Sparse Reconstruction with Compressed Sensing

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search

Author: Ngoc Ly (SysEn 5800 Fall 2021)

Compressed Sensing (CS)

Compressed Sensing summary here

Compression is synonymous with sparsity. So when we talk about compression we are actually referring to the sparsity. We introduce Compressed Sensing and then focus on reconstruction.

Three big groups of algorithms are:[1]

Optimization methods: includes minimization i.e. Basis Pursuit, and quadratically constraint minimization i.e. basis pursuit denoising.

greedy include Orthogonal matching pursuit and Compressive Sampling Matching Pursuit (CoSaMP)

thresholding-based methods such as Iterative Hard Thresholding(IHT) and Iterative Soft Thresholding, Approximate IHT or AM-IHT, and many more.

More cutting-edge methods include dynamic programming.

We will cover one, i.e. IHT. WHY IHT THEN? Basis pursuit, matching pursuit type algorithms belong to a more general class of iterative thresholding algorithms.Cite error: Closing </ref> missing for <ref> tag

[2]


[3]

[4]

[1]


[5]


[6]


[7]

[8]

[9]

  1. ↑ 1.0 1.1 7. Simon Foucart and Holger Rauhut. A mathematical introduction to compressive sens- ing. Applied and numerical harmonic analysis. Birkhäuser, New York [u.a.], 2013.
  2. ↑ 2. Emmanuel J. Candès and Terence Tao. Decoding by linear programming. IEEE Trans. Inf. Theory, 51(12):4203–4215, 2005.
  3. ↑ 5. Stephen A. Vavasis. Elementary proof of the spherical section property for random matrices. Univer-sity of Waterloo, Waterloo,Technical report, 2009.
  4. ↑ 6. Angshul Majumdar. Compressed sensing for engineers. Devices, circuits, and systems. CRC Press, Taylor & Francis Group, Boca Raton, FL, 2019. Includes bibliographical references and index.
  5. ↑ 8. D. L. Donoho. Compressed sensing. 52:1289–1306, 2006.
  6. ↑ 12. E. J. Candes, J. Romberg, and T. Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. 52:489–509, 2006.
  7. ↑ 16. Giulio Coluccia, Chiara Ravazzi, and Enrico Magli. Compressed sensing for dis- tributed systems, 2015.
  8. ↑ 17. Mohammed Rostami. Compressed sensing with side information on feasible re- gion, 2013.
  9. ↑ 18. Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for com- pressed sensing. May 2008.
Retrieved from "https://optimization.cbe.cornell.edu/index.php?title=Sparse_Reconstruction_with_Compressed_Sensing&oldid=4627"