Paper Info
Title
Fast and RIP-Optimal Transforms
Abstract
We study constructions of $$k \times n$$k n matrices $$A$$A that both (1) satisfy the restricted isometry property (RIP) at sparsity $$s$$s with optimal parameters, and (2) are efficient in the sense that only $$O(n\log n)$$O(nlogn) operations are required to compute $$Ax$$Ax given a vector $$x$$x. Our construction is based on repeated application of independent transformations of the form $$DH$$DH, where $$H$$H is a Hadamard or Fourier transform and $$D$$D is a diagonal matrix with random $$\{+1,-1\}$${+1,-1} elements on the diagonal, followed by any $$k \times n$$k n matrix of orthonormal rows (e.g. selection of $$k$$k coordinates). We provide guarantees (1) and (2) for a regime of parameters that is comparable with previous constructions, but using a construction that uses Fourier transforms and diagonal matrices only. Our main result can be interpreted as a rate of convergence to a random matrix of a random walk in the orthogonal group, in which each step is obtained by a Fourier transform $$H$$H followed by a random sign change matrix $$D$$D. After a few number of steps, the resulting matrix is random enough in the sense that any arbitrary selection of rows gives rise to an RIP matrix for, sparsity as high as slightly below $$s=\sqrt{n}$$s=n, with high probability. The proof uses a bootstrapping technique that, roughly speaking, says that if a matrix $$A$$A has some suboptimal RIP parameters, then the action of two steps in this random walk on this matrix has improved parameters. This idea is interesting in its own right, and may be used to strengthen other constructions.
Year
DOI
Venue
2013
10.1007/s00454-014-9632-3
Discrete & Computational Geometry
Keywords
DocType
Volume
Restricted isometry,Johnson–Lindenstrauss transformations,Compressive sensing
Journal
52
Issue
ISSN
Citations 
4
0179-5376
3
PageRank 
References 
Authors
0.40
15
2
Name
Order
Citations
PageRank
Nir Ailon1111470.74
Holger Rauhut281667.21