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
obtained by sampling random rows of a Discrete Fourier Tranform. How large does
need to be in order for, with high probability,
to satisfy the
-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
, there exists an Equiangular tight frame with
vectors in
dimensions. (or, there exist
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.
Relax and Conquer 