# 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?).