Fast and RIP-optimal transforms (Q2514234)

The authors study constructions of \(k\times n\) matrices \(A\) that both (1) satisfy the restricted isometry property (RIP) at sparsity \(s\) with optimal parameters, and (2) are efficient in the sense that only \(O(n\log n)\) operations are required to compute \(Ax\), given a vector \(x\). The construction is based on repeated application of independent transformations of the form \(DH\), where \(H\) is a Hadamard or Fourier transform and \(D\) is a diagonal matrix with random \(\{+1,-1\}\) elements on the diagonal, followed by any \(k\times n\) matrix of orthonormal rows (e.g. selection of \(k\) coordinates). They 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. The 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\) followed by a random sign change matrix \(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}\), with high probability. The proof uses a bootstrapping technique that, roughly speaking, says that if a matrix \(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.