lect-1压缩感知和稀疏优化基本理论.pdf

Lecture: Introduction to Compressed Sensing Sparse Recovery Guarantees /~wenzw/bigdata2016.html Acknowledgement: this slides is based on Prof. Emmanuel Candes’ and Prof. Wotao Yin’s lecture notes Underdetermined systems of linear equations n m n m x A b When fewer equations than unknowns Fundamental theorem of algebra says that we cannot find x In general, this is absolutely correct 2/41 Special structure If unknown is assumed to be sparse low-rank then one can often find solutions to these problems by convex optimization 3/41 Compressive Sensing /~wenzw/courses/sparse_l1_example.m Find the sparest solution Given n=256, m=128. A = randn(m,n); u = sprandn(n, 1, 0.1); b = A*u; 1 1 0.8 0.8 0.4 0.6 0.6 0.4 0.2 0.4 0.2