NTNU's Onsager Lecture, Compressed Sensing by Terence Tao, part 4 of 7

NTNU's Onsager Lecture, Compressed Sensing by Terence Tao, part 4 of 7.

Terence Tao was awarded the Onsager Medal at the Norwegian University of Science and Technology in December 2008. An unedited version of Tao's lecture on compressed sensing can be found here: http://multimedie.adm.ntnu.no/mediasite/Viewer/?peid=dffa743e1d7446...


Read more about the Onsager award here: http://www.ntnu.no/onsager

Category:

Education

Tags:

• NTNU
• Terence
• Tao
• Terry
• Lars
• Onsager
• The
• Norwegian
• University
• of
• Science
• and
• Technology
• maths
• mathematics
• Trondheim
• Norway
• lecture
• course
• seminar
• helge
• holden

[CaptainZeep]

He keeps referring to applications of CS (MRI, seismology) of which he hasn't even a superficial understanding:

MRI has nothing to do with passing neutron beams through a body!

Seismology has nothing to do with radar waves!

Geologic strata are not, in general, separated by fault planes!

In the future, he might want to spend like 10 minutes on Wikipedia before lecturing publicly on subjects of which he knows nothing.

[anirudh582]

@szproxy: with 2S measurements 'b', we have 2S equations but 'N' unknowns 'x'. But we know that (from the lemma proved before) that there can only be one unique solution with sparsity 'S' which is the sparsest of all the infinitely many N-dimensional solutions.

[szproxy]

Why do we choose to pick the sparsiest one to be the solution of Ax=b?

[dyonisiusdony]

also in 4.32. The S sparse solution means that we have AT MOST S non zero terms right? So the Brute force methods do not only loop over all (n S) possible collections of S columns, it must also search over (n S-1) possible collection of S-1 columns, (n S-2) possible collection of S-2 columns etc until (n 1) possible single column to find the solution. Am I right?

[dyonisiusdony]

.I would prefer to assume that we have three dimensional axis and the 3D ball to illustrate the l2 norm then for the line where all x that fullfil Ax=b lies, I would draw the line touches the one axis only. What I mean we can assume that the intersection between the line and the horizontal axis in the picture is not an intersection but actually as the line below the axis (if we see it in 3D space)

[dyonisiusdony]

The picture in 2.49 is very tricky example. I mean if you have good A that follows the Lemma in the pervious Lecture (part 3), then you should not have two points in the axis (x in the vertical axis and the other one in the horizontal axis). Otherwise, the minimization of l0 norm in the picture would not give the unique solution