8 added 253 characters in body

Does compressed sensing count as math? If it does, here is a blog post from the horse's mouth.

Edit: For those who would like a popular article, here is a good one in Wired (by JSE if I'm not mistaken). Also, it is encouraged to read the highly upvoted comment by JSE below.

Because I don't think I can ever explain it better than Terence Tao's brilliant blog post or think I'm qualified either, I'll just refer to the blog, and here simply mention in which field I, as someone working on combinatorial design theory, personally stumbled on it as an interactions between fields (Please read the following only when you have nothing better to do.). I hope experts edit and improve this post.

I had heard good things about compressed sensing before, but the first paper I read was about its application to error correction by Candes, Rudelson, Tao, and Vershynin. I don't know if it's comparable to other recent truly remarkable progress in coding/information theory (e.g., polar coding, which could be a candidate for the answer to OP's question), but it was a refreshing read to me who dabble in coding theory. It's in one sense similar to normal linear codes in that the goal is to recover a vector $f \in R^n$ by knowing $y = Af +e$, where $A$ is an $m$ by $n$ matrix and $e \in R^m$ is the error vector. But the paper studies when $f$ is uniquely determined by $l_1$-minimization a la compressed sensing. Then I learned that some combinatorial design theorists I follow were applying design theory to compressed sensing, in a very rough sense, to give a nice deterministic method for explicitly providing ideal $A$. And when I checked what was up in quantum information these days (I also dabble in quantum information), I ran into this paper by Gross, Liu, Flammia, Becker, and Eisert, where compressed sensing is applied to quantum state tomography, a method for determining the quantum state of a system. And this is the one paragraph version of how I wound up with an endless to-read backlog of papers spanning multiple fields.

7 added 95 characters in body; deleted 1 characters in body; edited body

Does compressed sensing count as math? If it does, here is a blog post from the horse's mouth.

Because I don't think I can ever explain it better than Terrence Terence Tao's brilliant blog post or think I'm qualified either, I'll just refer to the blog, and here simply mention in which field I, as someone working on combinatorial design theory, personally stumbled on it as an interactions between fields (Please read the following only when you have nothing better to do.). I hope experts edit and improve this post.

I had heard good things about compressed sensing before, but the first paper I read was about its application to error correction by Candes, Rudelson, Tao, and Vershynin. I don't know if it's comparable to other recent truly remarkable progress in coding/information theory (e.g., polar coding, which could be a candidate for the answer to OP's question), but it was a refreshing read to me who dabble in coding theory. It's in one sense similar to normal linear codes in that the goal is to recover a vector $f \in R^n$ by knowing $y = Ay Af +e$, where $A$ is an $m$ by $n$ matrix and $e \in R^m$ is the error vector. But the paper studies when $f$ is uniquely determined by $l_1$-minimization a la compressed sensing. Then I learned that some combinatorial design theorists I follow were applying design theory to compressed sensing. , in a very rough sense, to give a nice deterministic method for explicitly providing ideal $A$. And when I checked what was up in quantum information these days (I also dabble in quantum information), I ran into this paper by Gross, Liu, Flammia, Becker, and Eisert, where compressed sensing is applied to quantum state tomography, a method for determining the quantum state of a system. And this is the one paragraph version of how I wound up with an endless to-read backlog of papers spanning multiple fields.

6 deleted 2294 characters in body

Because I don't think I can ever explain it better than Terrence Tao's brilliant blog post or think I'm qualified either, I'll just blatantly copy&paste an excerpt from Wikipediarefer to the blog, and also here simply mention in which field I, as someone working on combinatorial design theory, personally stumbled on it as an interactions between fields (Please read the following only when you have nothing better to do.). I hope experts edit and improve this post.

[Wikipedia says:] Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a signal processing technique for efficiently acquiring and reconstructing a signal, by finding solutions to underdetermined linear systems. This takes advantage of the signal's sparseness or compressibility in some domain, allowing the entire signal to be determined from relatively few measurements. This is analogous to the game of Sudoku, where the game's rules allow the player to deduce the value of every point on the board, despite knowing only a few initial samples...

...Several scientific fields used $L_1$ techniques. In statistics, the least-squares method was complemented by the $L_1$-norm, which was introduced by Laplace. Following the introduction of linear programming and Dantzig's simplex algorithm, the $L_1$-norm was used in computational statistics. In statistical theory, the $L_1$-norm was used by George W. Brown and later writers on median-unbiased estimators. It was used by Peter Huber and others working on robust statistics. The $L_1$-norm was also used in signal processing, for example, in the 1970s, when seismologists constructed images of reflective layers within the earth based on data that did not seem to satisfy the Nyquist–Shannon criterion. It was used in matching pursuit in 1993, the LASSO estimator by Robert Tibshirani in 1996 and basis pursuit in 1998. There were theoretical results describing when these algorithms recovered sparse solutions, but the required type and number of measurements were sub-optimal and subsequently greatly improved by compressed sensing.

Around 2004 Emmanuel Candès, Terence Tao and David Donoho discovered important results on the minimum number of data needed to reconstruct an image even though the number of data would be deemed insufficient by the Nyquist–Shannon criterion. This work is the basis of compressed sensing as currently studied...

...The field of compressive sensing is related to other topics in signal processing and computational mathematics, such as to underdetermined linear-systems, group testing, heavy hitters, sparse coding, multiplexing, sparse sampling, and finite rate of innovation. Imaging techniques having a strong affinity with compressive sensing include coded aperture and computational photography.

5 added 300 characters in body
4 added 31 characters in body
3 added 62 characters in body
2 added 3462 characters in body
Post Made Community Wiki by S. Carnahan
1