Reconstruction From Anisotropic Random Measurements

Author

Rudelson, M. ; Shuheng Zhou

Author_Institution

Dept. of Math., Univ. of Michigan, Ann Arbor, MI, USA

Volume

59

Issue

6

fYear

2013

fDate

Jun-13

Firstpage

3434

Lastpage

3447

Abstract

Random matrices are widely used in sparse recovery problems, and the relevant properties of matrices with i.i.d. entries are well understood. This paper discusses the recently introduced restricted eigenvalue (RE) condition, which is among the most general assumptions on the matrix, guaranteeing recovery. We prove a reduction principle showing that the RE condition can be guaranteed by checking the restricted isometry on a certain family of low-dimensional subspaces. This principle allows us to establish the RE condition for several broad classes of random matrices with dependent entries, including random matrices with sub-Gaussian rows and nontrivial covariance structure, as well as matrices with independent rows, and uniformly bounded entries.

Keywords

eigenvalues and eigenfunctions; sparse matrices; anisotropic random measurements; independent row; low dimensional subspace; nontrivial covariance structure; random matrices; reduction principle; restricted eigenvalue condition; restricted isometry; subGaussian row; uniformly bounded entry; Context; Covariance matrices; Eigenvalues and eigenfunctions; Estimation; Random variables; Sparse matrices; Vectors; $ell_{1}$ minimization; Design matrices with uniformly bounded entries; restricted eigenvalue (RE) conditions; sparsity; sub-Gaussian random matrices;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2013.2243201

Filename

6471235