Abstract
We study lattice bases where the angle between any basis vector and the linear subspace spanned by the other basis vectors is at least π/3 radians; we denote such bases as "nearly orthogonal." We show that a nearly orthogonal lattice basis always contains a shortest lattice vector. Moreover, we prove that if the basis vector lengths are "nearly equal," then the basis is the unique nearly orthogonal lattice basis up to multiplication of basis vectors by ±1. We also study random lattices generated by the columns of random matrices with n rows and m ≤ n columns. We show that if m ≤ en, with c ≈ 0.071, then the random matrix forms a nearly orthogonal basis for the random lattice with high probability for large n and almost surely as n tends to infinity. Consequently, the columns of such a random matrix contain the shortest vector in the random lattice. Finally, we discuss an interesting JPEG image compression application where nearly orthogonal lattice bases play an important role.
Original language | English (US) |
---|---|
Pages (from-to) | 199-219 |
Number of pages | 21 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 21 |
Issue number | 1 |
DOIs | |
State | Published - 2007 |
Keywords
- Compression
- JPEG
- Lattices
- Random lattice
- Shortest lattice vector
ASJC Scopus subject areas
- Applied Mathematics
- Discrete Mathematics and Combinatorics