Compressive Sensing and Structured Random Matrices
Holger Rauhut · 2010
Compressive sensing predicts that sparse vectors can be recovered efficiently from highly undersampled measurements. While it is well-understood by now that Gaussian random matrices provide optimal measurement matrices in this context, such “highly ” random matrices suffer from certain drawbacks: applications require more structure arising from physical or other constraints, and recovery algorithms such as greedy methods or algorithms for ℓ1-minimization demand fast matrix vector multiplies in order to make them feasible for large scale problems. In order to meet such desiderata, we study two types of structured random measurement matrices: partial random circulant matrices, and random sampling matrices associated to bounded orthonormal systems (e.g. random Fourier type matrices). The latter maybe used to study reconstruction problems in high spatial dimensions. Compressive Sensing. A vector x ∈ CN is called s-sparse if ‖x‖0:= #{ℓ, xℓ = 0} ≤ s. The ℓp-norm is defined as usual, ‖x‖p: = ( ∑ N ℓ=1 |xℓ | p) 1/p,