Compressed Sensing Meets Information Theory

Google Tech Talk
October 7, 2009

ABSTRACT

Presented by Dror Baron, Visiting Scientist, Technion - Israel Institute of Technology.

Traditional signal acquisition techniques sample band-limited analog signals above the Nyquist rate, which is related to the highest analog frequency in the signal. Compressed sensing (CS) is based on the revelation that optimization routines can reconstruct a sparse signal from a small number of linear projections of the signal. Therefore, CS-based techniques can acquire and process sparse signals at much lower rates. CS offers tremendous potential in applications such as broadband analog-to-digital conversion, where the Nyquist rate exceeds the state of the art.

Information theory has numerous insights to offer CS; I will describe several investigations along these lines. First, distributed compressed sensing (DCS) provides new distributed signal acquisition algorithms that exploit both intra- and inter-signal correlation structures in multi-signal ensembles. DCS is immediately applicable in sensor networks. Next, we leverage the remarkable success of graph reduction algorithms and LDPC channel codes to design low-complexity CS reconstruction algorithms.

Linear measurements play a crucial role not only in compressed sensing but in disciplines such as finance, where numerous noisy measurements are needed to estimate various statistical characteristics. Indeed, many areas of science and engineering seek to extract information from linearly derived measurements in a computationally feasible manner. Advances toward a unified theory of linear measurement systems will enable us to effectively process the vast amounts of data being generated in our dynamic world.

Category:

Science & Technology

Tags:

• google
• tech
• talk
• machine
• learning

[barondror]

Thanks for your GREAT comments! First, I've read Moore's original paper, and he was definitely discussing transistor counts. But many people *interpret* the "law" to refer to clock speeds, hard disk densities, and so on. Around 1999 people were even talking about internet data rates doubling every 100 days :-)

I'll need to express myself more precisely in the future, great catch!

And Nyquist is obviously *above* double the bandwidth. But are any real-world signals truly bandlimited?...

[snamepi]

After the credit was given, I can concentrate on the main theme and say - what a great talk!

[ThaFacka]

its acutally the same as our senses or senses from higher animals are working.

[bypasslogin]

TLDR

[kadmany]

In brief what is this lecture about?

A fast logarithm for 100k 15sec things?

[bluesrunthegame]

"as I mentioned"

[coolsnowmen]

Ugg, he gets Nyquist wrong too? Nyquist says you have to sample at more than twice the largest frequency component in your system; not exactly equal to. It seems pedantic, but one should get it wrong on a test, and one could get bad data in the RL.

[coolsnowmen]

It bothers me when technical people get moore's law wrong. Moore said nothing about clock rates, only about transistor/gate density on a chip.

[ilyakis84]

I think you got a very serious analysis there from the other talk-backers - regarding your character, motives, relationships with colleagues and students e.t.c.

It's strange that you missed this professional analysis.

[barondror]

Who are the psychologists? I must be missing something...

[ilyakis84]

Being Psychologists - it's interesting that you have the ability to understand this complicated technical stuff too.

Actually, Dror is a very serious and smart guy, and he's totally OK with his students, colleauges e.t..c.

And... I think that it could be useful to practice some modesty and not being too hasty to judge, basing on an immediate unbalanced impression.