NDLI: On Nearly Orthogonal Lattice Bases and Random Lattices

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Neelamani, Ramesh Dash, Sanjeeb Baraniuk, Richard G.
Copyright Year	2007
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 $\frac{\pi}{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 $\pm 1$. We also study random lattices generated by the columns of random matrices with n rows and $m \leq n$ columns. We show that if $m \leq c\,n$, with $c \approx 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.
Starting Page	199
Ending Page	219
Page Count	21
File Format	PDF
ISSN	08954801
DOI	10.1137/050635985
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	1
Volume Number	21
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2007-03-15
Access Restriction	Subscribed
Subject Keyword	Image processing shortest lattice vector Lattices and related structures JPEG lattices random lattice compression
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

ON NEARLY ORTHOGONAL LATTICE BASES AND RANDOM LATTICES (2007)

On nearly orthogonal lattice bases (2005).

On Polynomial-Factor Approximations to the Shortest Lattice Vector Length

JPEG compression history estimation for color images

On Nearly Orthogonal Lattice Bases

Multistage Lattice Vector Quantization for Hyperspectral Image Compression

Forensics of High Quality and Nearly Identical JPEG Image Recompression

Survey on JPEG compatible joint image compression and encryption algorithms

Results on lattice vector quantization with dithering

On Nearly Orthogonal Lattice Bases and Random Lattices

Similar Documents

ON NEARLY ORTHOGONAL LATTICE BASES AND RANDOM LATTICES (2007)

On nearly orthogonal lattice bases (2005).

On Polynomial-Factor Approximations to the Shortest Lattice Vector Length

JPEG compression history estimation for color images

On Nearly Orthogonal Lattice Bases

Multistage Lattice Vector Quantization for Hyperspectral Image Compression

Forensics of High Quality and Nearly Identical JPEG Image Recompression

Survey on JPEG compatible joint image compression and encryption algorithms

Results on lattice vector quantization with dithering

On Nearly Orthogonal Lattice Bases and Random Lattices