Reconstruction from Anisotropic Random Measurements

Mark Rudelson, Shuheng Zhou
Proceedings of the 25th Annual Conference on Learning Theory, PMLR 23:10.1-10.24, 2012.

Abstract

Random matrices are widely used in sparse recovery problems, and the relevant properties of matrices with i.i.d. entries are well understood. The current 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 subgaussian rows and non-trivial covariance structure, as well as matrices with independent rows, and uniformly bounded entries.

Cite this Paper

BibTeX
@InProceedings{pmlr-v23-rudelson12, title = {Reconstruction from Anisotropic Random Measurements}, author = {Rudelson, Mark and Zhou, Shuheng}, booktitle = {Proceedings of the 25th Annual Conference on Learning Theory}, pages = {10.1--10.24}, year = {2012}, editor = {Mannor, Shie and Srebro, Nathan and Williamson, Robert C.}, volume = {23}, series = {Proceedings of Machine Learning Research}, address = {Edinburgh, Scotland}, month = {25--27 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v23/rudelson12/rudelson12.pdf}, url = {https://proceedings.mlr.press/v23/rudelson12.html}, abstract = {Random matrices are widely used in sparse recovery problems, and the relevant properties of matrices with i.i.d. entries are well understood. The current 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 subgaussian rows and non-trivial covariance structure, as well as matrices with independent rows, and uniformly bounded entries.} }
Endnote
%0 Conference Paper %T Reconstruction from Anisotropic Random Measurements %A Mark Rudelson %A Shuheng Zhou %B Proceedings of the 25th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2012 %E Shie Mannor %E Nathan Srebro %E Robert C. Williamson %F pmlr-v23-rudelson12 %I PMLR %P 10.1--10.24 %U https://proceedings.mlr.press/v23/rudelson12.html %V 23 %X Random matrices are widely used in sparse recovery problems, and the relevant properties of matrices with i.i.d. entries are well understood. The current 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 subgaussian rows and non-trivial covariance structure, as well as matrices with independent rows, and uniformly bounded entries.
RIS
TY - CPAPER TI - Reconstruction from Anisotropic Random Measurements AU - Mark Rudelson AU - Shuheng Zhou BT - Proceedings of the 25th Annual Conference on Learning Theory DA - 2012/06/16 ED - Shie Mannor ED - Nathan Srebro ED - Robert C. Williamson ID - pmlr-v23-rudelson12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 23 SP - 10.1 EP - 10.24 L1 - http://proceedings.mlr.press/v23/rudelson12/rudelson12.pdf UR - https://proceedings.mlr.press/v23/rudelson12.html AB - Random matrices are widely used in sparse recovery problems, and the relevant properties of matrices with i.i.d. entries are well understood. The current 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 subgaussian rows and non-trivial covariance structure, as well as matrices with independent rows, and uniformly bounded entries. ER -
APA
Rudelson, M. & Zhou, S.. (2012). Reconstruction from Anisotropic Random Measurements. Proceedings of the 25th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 23:10.1-10.24 Available from https://proceedings.mlr.press/v23/rudelson12.html.

Related Material