On the reduction of a random basis

Ali Akhavi; Jean-François Marckert; Alain Rouault

ESAIM: Probability and Statistics (2009)

  • Volume: 13, page 437-458
  • ISSN: 1292-8100

Abstract

top
For p ≤ n, let b1(n),...,bp(n) be independent random vectors in ℝ n with the same distribution invariant by rotation and without mass at the origin. Almost surely these vectors form a basis for the Euclidean lattice they generate. The topic of this paper is the property of reduction of this random basis in the sense of Lenstra-Lenstra-Lovász (LLL). If b ^ 1 ( n ) , ... , b ^ p ( n ) is the basis obtained from b1(n),...,bp(n) by Gram-Schmidt orthogonalization, the quality of the reduction depends upon the sequence of ratios of squared lengths of consecutive vectors r j ( n ) = ∥ b ^ n - j + 1 ( n ) ∥ 2 / ∥ b ^ n - j ( n ) ∥ 2 , j = 1,...,p - 1. We show that as n → +∡ the process ( r j ( n ) - 1 , j ≥ 1 ) tends in distribution in some sense to an explicit process ( ℛ j - 1 , j ≥ 1 ) ; some properties of the latter are provided. The probability that a random random basis is s-LLL-reduced is then showed to converge for p = n - g, and g fixed, or g = g(n) → +∞.

How to cite

top

Akhavi, Ali, Marckert, Jean-François, and Rouault, Alain. "On the reduction of a random basis." ESAIM: Probability and Statistics 13 (2009): 437-458. <http://eudml.org/doc/250640>.

@article{Akhavi2009,
abstract = {For p ≤ n, let b1(n),...,bp(n) be independent random vectors in $\mathbb\{R\}^n$ with the same distribution invariant by rotation and without mass at the origin. Almost surely these vectors form a basis for the Euclidean lattice they generate. The topic of this paper is the property of reduction of this random basis in the sense of Lenstra-Lenstra-Lovász (LLL). If $\widehat b_\{1\}^\{(n)\},\ldots, \widehat b_p^\{(n)\}$ is the basis obtained from b1(n),...,bp(n) by Gram-Schmidt orthogonalization, the quality of the reduction depends upon the sequence of ratios of squared lengths of consecutive vectors $r_j^\{(n)\} = \Vert \widehat b^\{(n)\}_\{n-j+1\}\Vert^2 / \Vert \widehat b^\{(n)\}_\{n-j\} \Vert^2$, j = 1,...,p - 1. We show that as n → +∡ the process $(r_j^\{(n)\}-1,j\geq 1)$ tends in distribution in some sense to an explicit process $(\{\mathcal R\}_j -1,j\geq 1)$; some properties of the latter are provided. The probability that a random random basis is s-LLL-reduced is then showed to converge for p = n - g, and g fixed, or g = g(n) → +∞. },
author = {Akhavi, Ali, Marckert, Jean-François, Rouault, Alain},
journal = {ESAIM: Probability and Statistics},
keywords = {Random matrices; random basis; orthogonality index; determinant; lattice reduction.; random matrices; lattice reduction; beta distribution; Gram-Schmidt orthogonalization},
language = {eng},
month = {9},
pages = {437-458},
publisher = {EDP Sciences},
title = {On the reduction of a random basis},
url = {http://eudml.org/doc/250640},
volume = {13},
year = {2009},
}

TY - JOUR
AU - Akhavi, Ali
AU - Marckert, Jean-François
AU - Rouault, Alain
TI - On the reduction of a random basis
JO - ESAIM: Probability and Statistics
DA - 2009/9//
PB - EDP Sciences
VL - 13
SP - 437
EP - 458
AB - For p ≤ n, let b1(n),...,bp(n) be independent random vectors in $\mathbb{R}^n$ with the same distribution invariant by rotation and without mass at the origin. Almost surely these vectors form a basis for the Euclidean lattice they generate. The topic of this paper is the property of reduction of this random basis in the sense of Lenstra-Lenstra-Lovász (LLL). If $\widehat b_{1}^{(n)},\ldots, \widehat b_p^{(n)}$ is the basis obtained from b1(n),...,bp(n) by Gram-Schmidt orthogonalization, the quality of the reduction depends upon the sequence of ratios of squared lengths of consecutive vectors $r_j^{(n)} = \Vert \widehat b^{(n)}_{n-j+1}\Vert^2 / \Vert \widehat b^{(n)}_{n-j} \Vert^2$, j = 1,...,p - 1. We show that as n → +∡ the process $(r_j^{(n)}-1,j\geq 1)$ tends in distribution in some sense to an explicit process $({\mathcal R}_j -1,j\geq 1)$; some properties of the latter are provided. The probability that a random random basis is s-LLL-reduced is then showed to converge for p = n - g, and g fixed, or g = g(n) → +∞.
LA - eng
KW - Random matrices; random basis; orthogonality index; determinant; lattice reduction.; random matrices; lattice reduction; beta distribution; Gram-Schmidt orthogonalization
UR - http://eudml.org/doc/250640
ER -

References

top
  1. J. Abbott and T. Mulders, How tight is Hadamard bound? Experiment. Math.10 (2001) 331–336.  
  2. A. Akhavi, Analyse comparative d'algorithmes de réduction sur les réseaux aléatoires. Ph.D. thesis, Université de Caen (1999).  
  3. A. Akhavi, Random lattices, threshold phenomena and efficient reduction algorithms. Theor. Comput. Sci.287 (2002) 359–385.  
  4. A. Akhavi, J.-F. Marckert and A. Rouault. On the reduction of a random basis, in D. Applegate, G.S. Brodal, D. Panario and R. Sedgewick Eds. Proceedings of the ninth workshop on algorithm engineering and experiments and the fourth workshop on analytic algorithmics and combinatorics. New Orleans (2007).  
  5. T.W. Anderson, An introduction to multivariate statistical analysis. Wiley Series in Probability and Statistics, Third edition. John Wiley (2003).  
  6. N.R. Chaganthy, Large deviations for joint distributions and statistical applications. Sankhya59 (1997) 147–166.  
  7. L. Chaumont and M. Yor, Exercises in probability. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2003).  
  8. H. Daudé and B. Vallée, An upper bound on the average number of iterations of the LLL algorithm. Theor. Comput. Sci.123 (1994) 95–115.  
  9. J.D. Dixon, How good is Hadamard's inequality for determinants? Can. Math. Bull.27 (1984) 260–264.  
  10. J.L. Donaldson, Minkowski reduction of integral matrices. Math. Comput.33 (1979) 201–216.  
  11. A. Edelman and N.R. Rao, Random matrix theory. Acta Numerica (2005) 1–65.  
  12. Y.H. Gan, C. Ling, and W.H. Mow, Complex Lattice Reduction Algorithm for Low-Complexity MIMO Detection. IEEE Trans. Signal Processing57 (2009) 2701–2710.  
  13. J. Hadamard, Résolution d'une question relative aux déterminants. Bull. Sci. Math.17 (1893) 240–246.  
  14. R. Kannan, Algorithmic geometry of numbers, in Annual review of computer science, Vol. 2. Annual Reviews, Palo Alto, CA (1987) 231–267.  
  15. D.E. Knuth, The art of computer programming, Vol. 2. Addison-Wesley Publishing Co., Reading, Mass., second edition. Seminumerical algorithms, Addison-Wesley Series in Computer Science and Information Processing (1981).  
  16. H. Koy and C.P. Schnorr, Segment LLL-Reduction of Lattice Bases. Lect. Notes Comput. Sci.2146 (2001) 67.  
  17. H.W. Lenstra Jr., Integer programming and cryptography. Math. Intelligencer6 (1984) 14–19.  
  18. H.W. Lenstra Jr., Flags and lattice basis reduction. In European Congress of Mathematics, Vol. I (Barcelona, 2000). Progr. Math.201 37–51. Birkhäuser, Basel (2001).  
  19. A.K. Lenstra, H.W. Lenstra Jr. and L. Lovász, Factoring polynomials with rational coefficients. Math. Ann.261 (1982) 515–534.  
  20. G. Letac, Isotropy and sphericity: some characterisations of the normal distribution. Ann. Statist.9 (1981) 408–417.  
  21. R.J. Muirhead, Aspects of multivariate statistical theory. John Wiley (1982).  
  22. H. Napias, A generalization of the LLL-algorithm over euclidean rings or orders. Journal de théorie des nombres de Bordeaux8 (1996) 387–396.  
  23. P.Q. Nguyen and J. Stern, The two faces of lattices in cryptology. In Cryptography and lattices (Providence, RI, 2001). Lect. Notes Comput. Sci.2146 (2001) 146–180. Springer.  
  24. A. Rouault, Asymptotic behavior of random determinants in the Laguerre, Gram and Jacobi ensembles. ALEA Lat. Am. J. Probab. Math. Stat.3 (2007) 181–230 (electronic).  
  25. C.P. Schnorr, A hierarchy of polynomial time basis reduction algorithms. Theory of algorithms, Colloq. Pécs/Hung, 1984. Colloq. Math. Soc. János Bolyai44 (1986) 375–386.  
  26. B. Vallée, Un problème central en géométrie algorithmique des nombres : la réduction des réseaux. Autour de l'algorithme de Lenstra Lenstra Lovasz. RAIRO Inform. Théor. Appl.3 (1989) 345–376. English translation by E. Kranakis in CWI-Quarterly - 1990 - 3.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.