# Compressed sensing and sampling

## A fancy ways of counting zero

Higgledy-piggledy notes on the theme of exploiting sparsity to recover signals from few non-local measurements, given that we know they are nearly sparse, in a sense that will be made clear soon.

## Basic Compressed Sensing

I’ll follow the intro of , which tries to unify many variants.

We attempt to recover a signal $$x_k\in \mathbb{R}^d$$ from $$m\ll n$$ measurements $$y_k$$ of the form

$y_k =\langle a_k, x\rangle + z_k,\, 1\leq k \leq m,$

or, as a matrix equation,

$y = Ax + z$

where $$A$$ is the $$m \times d$$ stacked measurement matrices, and the $$z$$ terms denote i.i.d. measurement noise.

Now, if $$x$$ is a sparse vector, and $$A$$ satisfies a restricted isometry property or something then we can construct an estimate $$\hat{x}$$ with small error by minimising

$\hat{x}=\min \|\dot{x}\|_1 \text{ subject to } \|A\dot{x}-y\|_2 < \varepsilon,$

where $$\varepsilon> \|z\|_2^2.$$

In the lecture notes on restricted isometry properties, Candès and Tao talk about not vectors $$x\in \mathbb{R}^d$$ but functions $$f:G \mapsto \mathbb{C}$$ on Abelian groups like $$G=\mathbb{Z}/d\mathbb{Z},$$ which is convenient for some phrasing, since then when I say my signal is $$s$$-sparse, which means that its support $$\operatorname{supp} \tilde{f}=S\subset G$$ where $$|S|=s$$.

In the finite-dimensional vector framing, we can talk about best sparse approximations $$x_s$$ to non-sparse vectors, $$x$$.

$x_s = \argmin_{\|\dot{x}\|_0\leq s} \|x-\dot{x}\|_2$

where all the coefficients apart from the $$s$$ largest are zeroed.

The basic results find attractive convex problems with high probability in a nest of nastier ones. There are also greedy optimisation versions, which are formulated as above, but no longer necessarily a convex optimisation; instead, we talk about Orthogonal Matching Pursuit, Iterative Thresholding and some other stuff the details of which I do not yet know, which I think pops up in wavelets and sparse coding.

For all of these the results tend to be something like

with data $$y,$$ the difference between my estimate of $$\hat{x}$$ and $$\hat{x}_\text{oracle}$$ is bounded by something-or-other where the oracle estimate is the one where you know ahead of time the set $$S=\operatorname{supp}(x)$$.

Candés gives an example result

$\|\hat{x}-x\|_2 \leq C_0\frac{\|x-x_s\|_1}{\sqrt{s}} + C_1\varepsilon$

conditional upon

$\delta_2s(A) < \sqrt{2} -1$

where this $$\delta_s(\cdot)$$ gives the restricted isometry constant of a matrix, defined as the smallest constant such that $$(1-\delta_s(A))\|x\|_2^2\leq \|Ax\|_2^2\leq (1+\delta_s(A))\|x\|_2^2$$ for all $$s$$-sparse $$))x$$. That is, the measurement matrix does not change the norm of sparse signals “much”, and in particular, does not null them when $$\delta_s < 1.$$

This is not the strongest bound out there apparently, but for any of that form, those constants look frustrating.

Measuring the restricted isometry constant of a given measurement matrix is presumably hard, although I haven’t tried yet. But generating random matrices that have a certain RIC with high probability is easy; that’s a neat trick in this area.

## Redundant compressed sensing

🏗 For now see Frame theory.

## Introductory texts

• Aside: see the rather good practical python notebook in numerical tours.

• Terry Tao’s exposition is great as usual. See, e.g.

[…] we can at least give an informal geometric argument as to why $$\ell^1$$ minimisation is more likely to recover a sparse solution than $$\ell^2$$ minimisation. The set of all $$f$$ whose Fourier coefficients match the observed data $$c_\xi$$ forms an affine subspace of the space of all functions. The $$\ell^2$$ minimiser can then be viewed geometrically by taking l^2 balls (i.e. Euclidean balls) centred at the origin, and gradually increasing the radius of the ball until the first point of contact with the affine subspace. In general, there is no reason to expect this point of contact to be sparse (i.e. to lie on a high-codimension coordinate subspace). If however we replace $$\ell^2$$ with $$\ell^1$$, then the Euclidean balls are replaced by octahedra, which are much “pointier” (especially in high dimensions) and whose corners lie on coordinate subspaces. So the point of first contact is now much more likely to be sparse. The idea of using $$\ell^1$$ as a “convex relaxation” of $$\ell^0$$ is a powerful one in applied mathematics; see for instance on the topic.

• Hegde, Baraniuk, Davenport and Duarte have an open source textbook

• Wes McKinney’s intro

• RIP vs JL

• Gabriel Peyre’s Compressed Sensing of Images

## …Using random projections

Classic. Notes under low dimensional projections

## …Using deterministic projections

Surely this is close to quasi monte carlo?

• Dustin G. Mixon Achieving the Welch bound with difference sets

I blogged about constructing harmonic frames using difference sets. We proved that such harmonic frames are equiangular tight frames, thereby having minimal coherence between columns. I concluded the entry by conjecturing that incoherent harmonic frames are as good for compressed sensing as harmonic frames whose rows were randomly drawn from the discrete Fourier transform (DFT) matrix

• A variant on the compressed sensing of Yves Meyer

recent work of Yves Meyer might be relevant:

• A variant on the compressed sensing of Emmanuel Candes, Basarab Matei and Yves Meyer

• Simple quasicrystals are sets of stable sampling, Basarab Matei and Yves Meyer

These papers are interesting because their approach to compressed sensing is very different. Specifically, their sparse vectors are actually functions of compact support with sufficiently small Lebesgue measure. As such, concepts like conditioning are replaced with that of stable sampling, and the results must be interpreted in the context of functional analysis. The papers demonstrate that sampling frequencies according to a (deterministic) simple quasicrystal will uniquely determine sufficiently sparse functions, and furthermore, the sparsest function in the preimage can be recovered by L1-minimization provided it’s nonnegative.

## Bayesian

Sparse Bayes can be tricky. See, perhaps, Bayesian Compressive Sensing.

## Phase transitions

How well can you recover a matrix from a certain number of measurements? In obvious metrics there is a sudden jump in how well you do with increasing measurements for a given rank. This looks a lot like a physical phase transition, which is a known phenomenon in ML. Hmm.

## Weird things to be classified

csgm, compressed sensing using generative models, tries to find a model which is sparse with respect to… some manifold of the latent variables of… a generative model? or something?

## References

Achlioptas, Dimitris. 2003. Journal of Computer and System Sciences, Special Issue on PODS 2001, 66 (4): 671–87.
Azizyan, Martin, Akshay Krishnamurthy, and Aarti Singh. 2015. arXiv:1506.00898 [Cs, Math, Stat], June.
Bach, Francis, Rodolphe Jenatton, and Julien Mairal. 2011. Optimization With Sparsity-Inducing Penalties. Foundations and Trends(r) in Machine Learning 1.0. Now Publishers Inc.
Baraniuk, Richard G. 2007. IEEE Signal Processing Magazine 24 (4).
———. 2008. IEEE Signal Processing Magazine 25 (2): 83–91.
Baraniuk, Richard G., Volkan Cevher, Marco F. Duarte, and Chinmay Hegde. 2010. IEEE Transactions on Information Theory 56 (4): 1982–2001.
Baraniuk, Richard, Mark Davenport, Ronald DeVore, and Michael Wakin. 2008. Constructive Approximation 28 (3): 253–63.
Baron, Dror, Shriram Sarvotham, and Richard G. Baraniuk. 2010. IEEE Transactions on Signal Processing 58 (1): 269–80.
Bayati, Mohsen, and Andrea Montanari. 2011. IEEE Transactions on Information Theory 57 (2): 764–85.
Berger, Bonnie, Noah M. Daniels, and Y. William Yu. 2016. Communications of the ACM 59 (8): 72–80.
Bian, W., and X. Chen. 2013. SIAM Journal on Optimization 23 (3): 1718–41.
Bingham, Ella, and Heikki Mannila. 2001. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 245–50. KDD ’01. New York, NY, USA: ACM.
Blanchard, Jeffrey D. 2013. Proceedings of the National Academy of Sciences 110 (4): 1146–47.
Bora, Ashish, Ajil Jalal, Eric Price, and Alexandros G. Dimakis. 2017. In International Conference on Machine Learning, 537–46.
Borgerding, Mark, and Philip Schniter. 2016. arXiv:1612.01183 [Cs, Math], December.
Bruckstein, A. M., Michael Elad, and M. Zibulevsky. 2008a. In 3rd International Symposium on Communications, Control and Signal Processing, 2008. ISCCSP 2008, 762–67.
———. 2008b. IEEE Transactions on Information Theory 54 (11): 4813–20.
Cai, T. Tony, Guangwu Xu, and Jun Zhang. 2008. arXiv:0805.0149 [Cs], May.
Cai, T. Tony, and Anru Zhang. 2015. The Annals of Statistics 43 (1): 102–38.
Candès, Emmanuel J. 2014. ICM 2014 Proceedings, to Appear.
Candès, Emmanuel J., and Mark A. Davenport. 2011. arXiv:1104.5246 [Cs, Math, Stat], April.
Candès, Emmanuel J., Yonina C. Eldar, Deanna Needell, and Paige Randall. 2011. Applied and Computational Harmonic Analysis 31 (1): 59–73.
Candès, Emmanuel J., and Benjamin Recht. 2009. Foundations of Computational Mathematics 9 (6): 717–72.
Candès, Emmanuel J., J. Romberg, and T. Tao. 2006a. IEEE Transactions on Information Theory 52 (2): 489–509.
Candès, Emmanuel J., Justin K. Romberg, and Terence Tao. 2006b. Communications on Pure and Applied Mathematics 59 (8): 1207–23.
Candès, Emmanuel J., and Terence Tao. 2006. IEEE Transactions on Information Theory 52 (12): 5406–25.
———. 2008. “The Uniform Uncertainty Principle and Compressed Sensing.”
Candès, Emmanuel J., and M.B. Wakin. 2008. IEEE Signal Processing Magazine 25 (2): 21–30.
Candès, Emmanuel, and Terence Tao. 2005. IEEE Transactions on Information Theory 51 (12): 4203–15.
Carmi, Avishy Y. 2013. Digital Signal Processing 23 (3): 751–70.
———. 2014. In Compressed Sensing & Sparse Filtering, edited by Avishy Y. Carmi, Lyudmila Mihaylova, and Simon J. Godsill, 281–324. Signals and Communication Technology. Springer Berlin Heidelberg.
Cevher, Volkan, Marco F. Duarte, Chinmay Hegde, and Richard Baraniuk. 2009. In Advances in Neural Information Processing Systems, 257–64. Curran Associates, Inc.
Chartrand, R., and Wotao Yin. 2008. In IEEE International Conference on Acoustics, Speech and Signal Processing, 2008. ICASSP 2008, 3869–72.
Chen, Xiaojun. 2012. Mathematical Programming 134 (1): 71–99.
Chen, Xiaojun, and Weijun Zhou. 2013. Computational Optimization and Applications 59 (1-2): 47–61.
Chretien, Stephane. 2008. arXiv:0809.0660 [Stat], September.
Dasgupta, Sanjoy. 2000. In Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence, 143–51. UAI’00. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.
Dasgupta, Sanjoy, and Anupam Gupta. 2003. Random Structures & Algorithms 22 (1): 60–65.
Dasgupta, Sanjoy, Daniel Hsu, and Nakul Verma. 2006. In Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence, 114–21. UAI’06. Arlington, Virginia, USA: AUAI Press.
Daubechies, I., M. Defrise, and C. De Mol. 2004. Communications on Pure and Applied Mathematics 57 (11): 1413–57.
Daubechies, Ingrid, Ronald DeVore, Massimo Fornasier, and C. Si̇nan Güntürk. 2010. Communications on Pure and Applied Mathematics 63 (1): 1–38.
DeVore, Ronald A. 1998. Acta Numerica 7 (January): 51–150.
Diaconis, Persi, and David Freedman. 1984. The Annals of Statistics 12 (3): 793–815.
Donoho, D. L., M. Elad, and V. N. Temlyakov. 2006. IEEE Transactions on Information Theory 52 (1): 6–18.
Donoho, David L. 2006. IEEE Transactions on Information Theory 52 (4): 1289–1306.
Donoho, David L., and Michael Elad. 2003. Proceedings of the National Academy of Sciences 100 (5): 2197–2202.
Donoho, David L., A. Maleki, and A. Montanari. 2010. In 2010 IEEE Information Theory Workshop (ITW), 1–5.
Donoho, David L., Arian Maleki, and Andrea Montanari. 2009a. Proceedings of the National Academy of Sciences 106 (45): 18914–19.
———. 2009b. In 2010 IEEE Information Theory Workshop (ITW), 1–5.
Duarte, Marco F., and Richard G. Baraniuk. 2013. Applied and Computational Harmonic Analysis 35 (1): 111–29.
Flammia, Steven T., David Gross, Yi-Kai Liu, and Jens Eisert. 2012. New Journal of Physics 14 (9): 095022.
Foygel, Rina, and Nathan Srebro. 2011. arXiv:1108.0373 [Math, Stat], August.
Freund, Yoav, Sanjoy Dasgupta, Mayank Kabra, and Nakul Verma. 2007. In Advances in Neural Information Processing Systems, 473–80.
Giryes, R., G. Sapiro, and A. M. Bronstein. 2016. IEEE Transactions on Signal Processing 64 (13): 3444–57.
Graff, Christian G., and Emil Y. Sidky. 2015. Applied Optics 54 (8): C23–44.
Hall, Peter, and Ker-Chau Li. 1993. The Annals of Statistics 21 (2): 867–89.
Harchaoui, Zaid, Anatoli Juditsky, and Arkadi Nemirovski. 2015. Mathematical Programming 152 (1-2): 75–112.
Hassanieh, Haitham, Piotr Indyk, Dina Katabi, and Eric Price. 2012. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 563–78. STOC ’12. New York, NY, USA: ACM.
Hassanieh, H., P. Indyk, D. Katabi, and E. Price. 2012. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 1183–94. Proceedings. Kyoto, Japan: Society for Industrial and Applied Mathematics.
Hegde, Chinmay, and Richard G. Baraniuk. 2012. IEEE Transactions on Information Theory 58 (12): 7204–14.
Hormati, A., O. Roy, Y.M. Lu, and M. Vetterli. 2010. IEEE Transactions on Signal Processing 58 (3): 1095–1109.
Hoyer, Patrik O. n.d. Journal of Machine Learning Research 5 (9): 1457–69.
Jaggi, Martin. 2013. In Journal of Machine Learning Research, 427–35.
Kabán, Ata. 2014. In Journal of Machine Learning Research, 448–56.
Kim, Daeun, and Justin P. Haldar. 2016. Signal Processing 125 (August): 274–89.
Lahiri, Subhaneil, Peiran Gao, and Surya Ganguli. 2016. arXiv:1607.04331 [Cs, q-Bio, Stat], July.
Launay, Julien, Iacopo Poli, François Boniface, and Florent Krzakala. 2020. In Advances in Neural Information Processing Systems, 33:15.
Li, Ping, Trevor J. Hastie, and Kenneth W. Church. 2006. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 287–96. KDD ’06. New York, NY, USA: ACM.
Li, Yingying, and Stanley Osher. 2009. Inverse Problems and Imaging 3 (3): 487–503.
Matei, Basarab, and Yves Meyer. 2010. Complex Variables and Elliptic Equations 55 (8-10): 947–64.
Mishali, Moshe, and Yonina C. Eldar. 2010. IEEE Journal of Selected Topics in Signal Processing 4 (2): 375–91.
Montanari, Andrea. 2012. Compressed Sensing: Theory and Applications, 394–438.
Mousavi, Ali, and Richard G. Baraniuk. 2017. In ICASSP.
Needell, D., and J. A. Tropp. 2008. arXiv:0803.2392 [Cs, Math], March.
Oka, A, and L. Lampe. 2008. In 5th IEEE Sensor Array and Multichannel Signal Processing Workshop, 2008. SAM 2008, 257–60.
Olshausen, B. A., and D. J. Field. 1996. Network (Bristol, England) 7 (2): 333–39.
Olshausen, Bruno A, and David J Field. 2004. Current Opinion in Neurobiology 14 (4): 481–87.
Oxvig, Christian Schou, Thomas Arildsen, and Torben Larsen. 2017. Aalborg University.
Pawar, Sameer, and Kannan Ramchandran. 2015. arXiv:1501.00320 [Cs, Math], January.
Peleg, Tomer, Yonina C. Eldar, and Michael Elad. 2010. IEEE Transactions on Signal Processing 60 (5): 2286–2303.
Qiuyun Zou, Haochuan Zhang, Chao-Kai Wen, Shi Jin, and Rong Yu. 2018. IEEE Signal Processing Letters 25 (12): 1835–39.
Rangan, Sundeep. 2011. In 2011 IEEE International Symposium on Information Theory Proceedings, 2168–72. St. Petersburg, Russia: IEEE.
Ravishankar, Saiprasad, and Yoram Bresler. 2015. arXiv:1501.02923 [Cs, Stat], January.
Ravishankar, S., and Y. Bresler. 2015. IEEE Transactions on Signal Processing 63 (9): 2389–2404.
Rish, Irina, and Genady Grabarnik. 2014. In Compressed Sensing & Sparse Filtering, edited by Avishy Y. Carmi, Lyudmila Mihaylova, and Simon J. Godsill, 77–93. Signals and Communication Technology. Springer Berlin Heidelberg.
Rish, Irina, and Genady Ya Grabarnik. 2015. Sparse Modeling: Theory, Algorithms, and Applications. Chapman & Hall/CRC Machine Learning & Pattern Recognition Series. Boca Raton, FL: CRC Press, Taylor & Francis Group.
Romberg, J. 2008. IEEE Signal Processing Magazine 25 (2): 14–20.
Rosset, Saharon, and Ji Zhu. 2007. The Annals of Statistics 35 (3): 1012–30.
Rubinstein, Ron, T. Peleg, and Michael Elad. 2013. IEEE Transactions on Signal Processing 61 (3): 661–77.
Sarvotham, Shriram, Dror Baron, and Richard G. Baraniuk. 2006. In In Proc. Allerton Conf. On Comm., Control, and Computing.
Schniter, P., and S. Rangan. 2012. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 815–22.
Shalev-Shwartz, Shai, and Ambuj Tewari. 2011. Journal of Machine Learning Research 12 (July): 1865–92.
Smith, Virginia, Simone Forte, Michael I. Jordan, and Martin Jaggi. 2015. arXiv:1512.04011 [Cs], December.
Song, Ruiyang, Yao Xie, and Sebastian Pokutta. 2015. arXiv:1509.00130 [Cs, Math, Stat], August.
Tropp, J. A., and S. J. Wright. 2010. Proceedings of the IEEE 98 (6): 948–58.
Tropp, J.A. 2006. IEEE Transactions on Information Theory 52 (3): 1030–51.
Vetterli, Martin. 1999. In AeroSense’99, 3723:28–31. International Society for Optics and Photonics.
Weidmann, Claudio, and Martin Vetterli. 2012. IEEE Transactions on Information Theory 58 (8): 4969–92.
Wipf, David, and Srikantan Nagarajan. 2016. Microsoft Research, July.
Wu, R., W. Huang, and D. R. Chen. 2013. IEEE Signal Processing Letters 20 (4): 403–6.
Wu, Yan, Mihaela Rosca, and Timothy Lillicrap. 2019. In International Conference on Machine Learning, 6850–60.
Yaghoobi, M., Sangnam Nam, R. Gribonval, and M.E. Davies. 2012. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 5409–12.
Yang, Wenzhuo, and Huan Xu. 2015. In Journal of Machine Learning Research, 494–503.
Zhang, Kai, Chuanren Liu, Jie Zhang, Hui Xiong, Eric Xing, and Jieping Ye. 2017. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 615–23. KDD ’17. New York, NY, USA: ACM.

### No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.