What are the main open problems in compressed sensing?
I am interested in theoretical as well as in numerical point of view.
[Math] Open problems in compressed sensing
co.combinatoricscompressed sensinglinear algebraopen-problems
Related Solutions
These are some big problems I know about:
$e$-positivity of Stanley's chromatic-symmetric functions for incomparability graphs obtained from $3+1$-avoiding posets. Shareshian and Wachs have some recent results related to this that connects these polynomials to representation theory, and they refine this conjecture with a $q$-parameter. Note that Schur-positivity is already known, and that the $e_\lambda$ expands positively into Schurs. It all boils down to finding a partition-valued combinatorial statistic on certain acyclic orientations.
Give a combinatorial description of the Kronecker coefficients.
- Find a combinatorial interpretation of the Littlewood-Richardson coefficients for the Jack polynomials, $J_{\mu} J_{\nu} = \sum_\lambda c^\lambda_{\mu\nu}(\alpha) J_\lambda$. It is conjectured (but not proved) that $c^\lambda_{\mu\nu}(\alpha)$ is a polynomial in $\alpha$ with non-negative integer coefficients. (Here, one needs to be a bit careful with which normalization one chooses).
Find a combinatorial description of the multiplicative structure constants for the Schubert polynomials (analogue of the Littlewood-Richardson coefficients in the Schur polynomial case).
The different variants of the shuffle conjecture. UPDATE: There is a recent proof on arxiv. There are still some generalizations of this that remains unproved.
Prove that LLT polynomials have positive Schur expansion. This is related to the shuffle conjecture and the $qt$-Kostka polynomials, see N. Loehr's notes.
Give a combinatorial formula for the non-homogeneous symmetric Jack polynomials (similar to the Knop-Sahi formula for the ordinary Jack polynomials).
Give combinatorial descriptions of structure constants that appear in plethystic substitutions, $a^\nu_{\lambda\mu} = \langle s_\lambda[s_\mu], s_\nu \rangle$
Find a combinatorial description of the $qt$-Kostka polynomials.
Find a combinatorial description of the polynomials $c^\nu_{\lambda\mu}(t)$ in $$s_\lambda(t) \cdot P_\mu(x;t) = \sum_\nu c^\nu_{\lambda\mu}(t) P_\mu(x;t)$$ where $P_\lambda(x;t)$ is the Hall-Littlewood polynomial.
Prove (or disprive) that the map $k \mapsto K_{k\lambda,k\mu}$ is a polynomial with non-negative coefficients, where $K_{\lambda\mu}$ is the Kostka coefficient. Or in more general, same question for $k \mapsto c^{k\nu}_{k\lambda,k\mu}$ for the Littlewood-Richardson coefficients. This question goes back to King, Tollu and Toumazet. Note that a proof of the latter would imply the famous saturation conjecture proved by A. Knutson and T. Tao. The conjecture is stated in Rassart's paper, here, where the polynomiality property is proved.
I have looked on the special case concerning Koskta coefficients, and this lead me to ask this somewhat related question. The negative answer to this question hints that the positivity conjecture might possibly be false, but a minimal counter example lives in a very high dimension, out of reach by exhaustive computer search. This concerns Ehrhart polynomials for non-integral polytopes, and very little is know about this case. One can show that such Ehrhart (quasi)polynomials have properties that Ehrhart polynomials corresponding to integral polytopes lack.
Whenever one seeks a combinatorial description, it is understood that the polynomial or number in question is conjectured to be a polynomial with non-negative integer coefficients.
[Just 'cause Artie asked:] :)
Many parts of the mmp are not know for log canonical pairs. There are many results in that direction, but also many questions are open. In some sense log canonical is a more natural class than klt or even dlt and it is very important from the point of view of applications to moduli theory because semi log canonical (the non-normal version of lc) singularities are closed under stable degeneration while klt singularities are not. A major difficulty stems from the fact that lc singularities are not rational.
Best Answer
A relatively recent (2012) overview of open problems and challenges in compressive sensing has been written by Thomas Strohmer. A somewhat older (2007) listing by Terence Tao is still timely: