Capacity bounds for the CDMA system and a neural network : a moderate deviations approach

Löwe, Matthias; Vermet, Franck

ESAIM: Probability and Statistics, Tome 13 (2009), pp. 343-362.

Nous étudions deux systèmes basés sur des sommes de variables aléatoires de Bernoulli valant $\pm$ 1 avec égale probabilité et faiblement dépendantes. Nous montrons qu’une seule étape de la méthode de suppression d’interférences SD-PIC, utilisée dans la troisième génération de télécommunication mobile CDMA, permet déjà d’augmenter considérablement le nombre d’utilisateurs supporté par le système. Nous considérons également une variante du modèle neuronal de Hopfield. Nous montrons que cette variante, proposée par Amari et Yanai [2], admet une capacité de stockage supérieure au modèle original. Les deux situations conduisent à l’étude des déviations modérées d’une somme de variables aléatoires de Bernoulli faiblement corrélées. Nous montrons un principe de déviations modérées pour une telle somme convenablement normalisée.

We study two systems that are based on sums of weakly dependent Bernoulli random variables that take values $\pm$ 1 with equal probabilities. We show that already one step of the so-called soft decision parallel interference cancellation, used in the third generation of mobile telecommunication CDMA, is able to considerably increase the number of users such a system can host. We also consider a variant of the well-known Hopfield model of neural networks. We show that this variant proposed by Amari and Yanai [2] has a larger storage capacity than the original model. Both situations lead to the question of the moderate deviations behavior of a sum of weakly dependent Bernoulli random variables. We prove a moderate deviations principle for such a sum on the appropriate scale.

Classification : 82C32, 82B44, 60K35, 94A05, 94A15
Mots clés : moderate deviations, large deviations, neural networks, storage capacity, Hopfield model, code division multiple access (CDMA) systems, parallel interference cancellation

[1] B. Aazhang and M.K. Varanasi, Multistage detection in asynchronous code division multiple acces communications. IEEE Trans. Commun. 38 (1990) 509-519.

[2] S. Amariand and H.-F. Yanai, Auto-associative memory with two-stage dynamics of nonmonotonic neurons. IEEE Trans. Neural Networks 7 (1996) 803-815.

[3] R.K. Bahr and J.S. Sadowski, Direct-sequence spread-spectrum multiple-access communications with random signature sequences: A large deviations analysis. IEEE Trans. Inform. Theory 37 (1991) 514-527.

[4] A. Ben-Israel and A. Charnes, Contribution to the theory of generalized inverses. J. SIAM 11 (1963) 667-699. | MR | Zbl

[5] A. Bovier, Sharp upper bounds for perfect retrieval in the Hopfield model. J. Appl. Probab. 36 (1999) 941-950. | MR | Zbl

[6] A. Bovier, Statistical mechanics of disordered system: A mathematical perspective. Cambridge Series in Statistical and Probabilistic Mathematics 18. Cambridge University Press (2006). | MR | Zbl

[7] A. Bovier and V. Gayrard, Hopfield models as a generalized mean field model, preprint. In Mathematics of spin glasses and neural networks, A. Bovier and P. Picco (Eds.). Progress in Probability, Birkhäuser (1998). | MR | Zbl

[8] R.M. Buehrer and B.D. Woerner, Analysis of adaptive multistage interference cancellation for CDMA using an improved Gaussian approximation. IEEE Trans. Commun. 44 (1996) 1308-1329.

[9] R.M. Buehrer, A. Kaul, S. Striglis and B.D. Woerner, Analysis of DS-CDMA parallel interference cancellation with phase and timing errors. IEEE JSAC 14 (1996) 1522-1535.

[10] B. Crespi, Storage capacity of non-monotonic neurons. Neural Networks 12 (1999) 1377-1389.

[11] P. De Jong, A Central Limit Theorem for Generalized Multilinear Forms. J. Multiv. Anal. 34 (1990) 275-289. | MR | Zbl

[12] G. Dreyfus, I. Guyon and L. Personnaz, Information storage and retrieval in spin-glass like neural networks. J. Phys. Lett. 46 (1985) L359-L365.

[13] G. Dreyfus, I. Guyon and L. Personnaz, Collective computational properties of neural networks: New learning mechanisms. Phys. Rev. A 34 (1986) 4217-4228. | MR

[14] P. Eichelsbacher and M. Löwe, A large deviation principle for $m$-variate von Mises-statistics and $U$-statistics. J. Theoret. Probab. 8 (1995) 807-824. | MR | Zbl

[15] P. Eichelsbacher and M. Löwe, Moderate deviations for i.i.d. random variables. ESAIM: PS 7 (2003) 209-218. | Numdam | MR | Zbl

[16] J.M. Holtzman, A simple, accurate method to calculate spread spectrum multiple-access error probabilities. IEEE Trans. Commun. 40 (1992) 461-464. | Zbl

[17] J.J. Hopfield, Neural networks and physical systems with emergent collective computational abilities. Proc. Natl. Acad. Sci. USA 79 (1982) 2554-2558. | MR

[18] M. Juntti, Multiuser demodulation for DS-CDMA systems in fading channels, Ph.D. thesis, University of Oulu, Finland, 1998.

[19] I. Kanter and H. Sampolinski, Associative recall of memory without errors. Phys. Rev. A 35 (1987) 380-392.

[20] M.J. Klok, G. Hooghiemstra, T. Ojanperä and R. Prasad, A novel technique for DS-CDMA system performance evaluation. VTC'99 spring, Houston, USA (1999).

[21] K. Kobayashi, On the capacity of a neuron with a nonmonotone output function. Network 2 (1991) 237-243. | MR

[22] W. König and P. Mörters, Brownian intersection local times: Upper tail asymptotics and thick points. Ann. Probab. 30 (2002) 1605-1656. | MR | Zbl

[23] M Latva-Aho, Advanced receivers for wideband CDMA systems, Ph.D. thesis, University of Oulu, Finland, 1999.

[24] J.S. Lehnert and M.B. Pursley, Error probabilities for binary direct sequence spread-spectrum communications with random signature sequences. IEEE Trans. Commun. COM-35 (1987) 87-98.

[25] J.S. Lehnert and R.K. Morrow, Bit-to-bit-error dependence in slotted DS/SSMA packet systems with random signature sequences. IEEE Trans. Commun. COM-37 (1989) 1052-1061.

[26] M. Löwe, On the storage capacity of Hopfield models with weakly correlated patterns. Ann. Appl. Probab. 8 (1999) 1216-1250. | Zbl

[27] M. Löwe and F. Vermet, The storage capacity of the Hopfield model and moderate deviations. Statist. Probab. Lett. 75 (2005) 237-248. | MR | Zbl

[28] M. Löwe and F. Vermet, The Capacity of $q$-state Potts neural networks with parallel retrieval dynamics. Statist. Probab. Lett. 77 (2007) 1505-1514. | MR | Zbl

[29] Mathematical aspects of spin glasses and neural networks, in A. Bovier and P. Picco (Eds.). Progress in Probability, Birkhäuser, Boston (1998). | MR | Zbl

[30] R. Mceliece, E. Posner, E. Rodemich and S. Venkatesh, The capacity of the Hopfield associative memory. IEEE Trans. Inform. Theory 33 (1987) 461-482. | MR | Zbl

[31] S.K. Mitra and C.R. Rao, Generalized inverse of matrices and its applications. Wiley, New York (1971). | MR | Zbl

[32] M. Morita, Associative memory with nonmonotone dynamics. Neural Networks 6 (1993) 115-126.

[33] M. Morita, S. Yoshizawa and K. Nakano, Analysis and improvement of the dynamics of autocorrelation associative memory. Trans. Inst. Electron. Inform. Commun. Eng. Jpn J73-D-II (1990) 232-242.

[34] N. Nishimori and I. Opris, Retrieval process of an associative memory with nonmonotonic input-output function. IEEE Int. Conf. Neural Networks 1 (1993) 353-358.

[35] G. Palm, Memory capacities of local rules for synaptic modification. Concepts Neurosci. 2 (1991) 97-128.

[36] L.A. Pastur and A.L. Figotin, Exactly soluble model of a spin-glas. Sov. J. Low Temp. Phys. 3 (1977) 378-383.

[37] D. Petritis, Thermodynamic formalism of neural computing; Nonlinear Phenomena of Complex Systems, volume 2, pp. 86-146. Kluwer Acad. Publ., Dordrecht (1996). | MR | Zbl

[38] P. Picco, Artificial neural networks. A review from Physical and Mathematical point of view. Ann. Inst. H. Poincaré, Section A 64 (1996) 289-307. | Numdam | MR | Zbl

[39] R. Prasad, CDMA for wireless personal communications. Artech House (1996).

[40] E. Rio, Théorie asymptotique des processus aléatoires faiblement dépendants. Springer (Ed.), Paris (2000). | MR | Zbl

[41] M.O. Sunay and P.J. Mclane, Calculating error probabilities for DS CDMA systems: When not to use the Gaussian approximation. IEEE Globecom 3 (1996) 1744-1749.

[42] R. Van Der Hofstad and M.J. Klok, Improving the performance of third-generation wireless communication systems. Adv. Appl. Probab. 36 (2004) 1046-1084. | MR | Zbl

[43] R. Van Der Hofstad, G. Hooghiemstra and M.J. Klok, Large deviations for code division multiple access systems. SIAM J. Appl. Math. 62 (2002) 1044-1065. | MR | Zbl

[44] R. Van Der Hofstad, M. Löwe and F. Vermet, The effect of system load on the existence of bit-errors in CDMA with and without parallel interference cancelation. IEEE Trans. Inform. Theory 52 (2006) 4733-4741. | MR

[45] F. Vermet, Étude asymptotique d'un réseau neuronal : le modèle de mémoire associative de Hopfield, Ph.D. thesis, University of Rennes 1, France, 1994.