[CSDM] [pvsnp-all] CCI meeting Apr 12 on compressed sensing/sparse recovery

[Moses S. Charikar]

Hi all,

We will have our monthly CCI meeting this Friday on 
Apr 12. This month's meeting is devoted to problems in 
compressed sensing/sparse recovery. We will have talks by 
three experts who will give us an overview of research in 
this area and outline open problems for future work.

As usual, we will meet in CS 402.

The program is as follows:

10:00-11:00 PI meeting (for PIs only)
11:00-12:00 Deanna Needell, Analysis and synthesis methods in compressed sensing
12:00- 1:00 lunch
 1:00- 2:00 Andrea Montanari, Finding cliques in large random graphs, sparse PCA and iterative thresholding
 2:00- 2:30 break
 2:30- 3:30 Piotr Indyk, Faster Algorithms for the Sparse Fourier Transform

See below for abstracts.

Best,
Moses


Analysis and synthesis methods in compressed sensing
Deanna Needell, Claremont McKenna College

In this talk we will discuss results for robust signal reconstruction
from random observations via synthesis and analysis methods.  Synthesis
methods attempt to identify the low-dimensional representation of the signal
directly, whereas analysis type methods reconstruct in signal space.
We also include provable near-optimal reconstruction guarantees for total-variation
minimization using properties of the bivariate Haar transform.


Finding cliques in large random graphs, sparse PCA and iterative thresholding
Andrea Montanari, Stanford

Consider a n times n symmetric matrix A, whose entries are i.i.d. with a common law P_0,
except for a small k times k submatrix whose entries are also i.i.d. but with a different law P_1.
We consider the case in which P_1 and P_0 have different mean, and investigate the problem
of identifying the 'anomalous' k by k submatrix. A special case of this question is the well studied
problem of identifying a clique in an Erdos-Renyi random graph.
A simple counting argument shows that such a submatrix can be uniquely identified via
exhaustive enumeration provided k is larger than C*log(n), for a suitable constant C.
Unfortunately, no practical algorithm is successful for k smaller than square root of n.
Worse than this, the best available guarantees are for vanilla PCA which does not make 
use of the sparsity of the submatrix.
I will describe an iterative thresholding algorithm that provably improves over simple PCA,
and in particular finds cliques of size square root of n/e.

[Joint work with Yash Deshpande]


Faster Algorithms for the Sparse Fourier Transform
Piotr Indyk, MIT

The Fast Fourier Transform (FFT) is one of the most fundamental numerical
algorithms. It computes the Discrete Fourier Transform (DFT) of an
n-dimensional signal in O(n log n) time. The algorithm plays an important role
in many areas. It is not known whether its running time can be improved.
However, in many applications, most of the Fourier coefficients of a
signal are "small" or equal to zero, i.e., the output of the transform is (approximately)
sparse. In this case, it is known that one can compute the set of non-zero
coefficients faster than in O(n log n) time.

In this talk, I will describe a new set of efficient algorithms for sparse
Fourier Transform. One of the algorithms has the running time of O(k log n),
where k is the number of non-zero Fourier coefficients of the signal. This
improves over the runtime of the FFT for any k = o(n). If time allows, I will
also describe some of the applications, to spectrum sensing
and GPS locking, as well as mention a few outstanding open problems.

The talk will cover the material from the joint papers with Fadel Adib, Badih
Ghazi, Haitham Hassanieh, Dina Katabi, Eric Price and Lixin Shi. 


The papers are available at http://groups.csail.mit.edu/netmit/sFFT/


 
_______________________________________________
pvsnp-all mailing list
pvsnp-all at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/pvsnp-all