18.S096: Compressed Sensing and Sparse Recovery

Another set of Lecture notes for my course, this time about Compressed Sensing and Sparse Recovery, is available here. As usual, I will document the open problems here, while referring to a much more detailed description of the problems on the notes, including description of partial progress.

Open Problem 6.1. (Random Partial Discrete Fourier Transform)

Consider a A\in\mathbb{C}^{M\times N} obtained by sampling random rows of a Discrete Fourier Tranform. How large does M need to be in order for, with high probability,  A to satisfy the (s,\frac13)-RIP?


Open Problem 6.2. (Mutually Unbiased Bases)

How many mutually unbiased bases are there in 6 dimensions?


Open Problem 6.3. (Zauner’s Conjecture)

Prove or disprove the SIC-POVM / Zauner’s conjecture: For any d, there exists an Equiangular tight frame with d^2 vectors in \mathbb{C}^d dimensions. (or, there exist d^2 equiangular lines in \mathbb{C}^d).


Open Problem 6.4. (The Paley ETF Conjecture)

Does the Paley Equiangular tight frame satisfy the Restricted Isometry Property pass the square root bottleneck? (even by logarithmic factors?).


Open Problem 6.5. (Constructive Kadison-Singer)

Give a (polynomial time) construction of the tight frame partition satisfying the properties required in the Kadison-Singer problem (or the related Weaver’s conjecture). These partitions were proven to exist (with a non-constructive proof) in the recent breakthrough of Marcus, Spielman, and Srivastava.



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s