On nearly orthogonal lattice bases and random lattices

Ramesh Neelamani, Sanjeeb Dash, Richard G. Baraniuk

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

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 languageEnglish (US)
Pages (from-to)199-219
Number of pages21
JournalSIAM Journal on Discrete Mathematics
Volume21
Issue number1
DOIs
StatePublished - 2007

Keywords

  • Compression
  • JPEG
  • Lattices
  • Random lattice
  • Shortest lattice vector

ASJC Scopus subject areas

  • Applied Mathematics
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On nearly orthogonal lattice bases and random lattices'. Together they form a unique fingerprint.

Cite this