133 problems

Let $p\equiv 1\pmod{4}$ be prime, let $\Phi_p$ be the Paley equiangular tight frame, and let $\delta_K=\delta_K(\Phi_p)$ denote its RIP constant of order $K$. Paley ETF RIP-constan…

Let $\boldsymbol{A}$ be a sensing matrix with restricted isometry constant $\delta_{K+1}$, and let $\boldsymbol{x}$ be a $K$-sparse signal. Dai–Milenkovic conjecture. There exist a…

Information-theoretic impossibility conjecture. Recovery is information-theoretically impossible no matter the sample size in the sub-linear sparsification regime where $d=o(p)$.

QMEGS is a quantum eigenvalue estimation algorithm, and OMP is an algorithm from compressed sensing. The authors observe a close connection between these methods. Compressed-sensin…

Let $p$ be an odd prime. The Paley matrix is a $(p+1)/2 \times (p+1)$ matrix defined by quadratic residues modulo $p$. A matrix has the $(K,\delta)$-restricted isometry property wh…

Optimality conjecture. The bound

Sharp-bound conjecture. For every $t$ satisfying $0<t<4/3$,

Logarithmic-factor conjecture. The factor $\sqrt{\log m}$ in this lower bound is simply a proof artifact.

Fix $s=O(1)$. Let $d$ be the representation width, $F$ the number of features, and let $\mathbf b\in\{0,1\}^F$ be an $s$-sparse Boolean feature vector. An input code is a matrix…

Let $f_i$ be more general discontinuous measurement functions, and consider uniform and nonuniform recovery error rates for structured signal recovery from nonlinear observations.…

Let Algorithm generate sequences $(x^k)_{k\in\mathds N}$ and $(z^k)_{k\in\mathds N}$ for the basis-pursuit problem. Convergence conjecture. Algorithm always converges to a solution…

Tight measurement-bound conjecture. The bound $4dr-4r^2$ is tight: if $m<4dr-4r^2$, then for every measurement family $\mathcal A=\{\mathbf A_j\}_{j=1}^m$, the map…

Splittability conjecture. All full-spark frames are $s$-splittable with sufficiently small $\beta>0$.

Let $\bm A$ be a measurement matrix and let $\bm x\in\mathbb{C}^n_s$ be an $s$-sparse complex signal. In phase-less measurements, one observes … where recovery is considered exact…

Legendre-symbol conjecture. The Legendre symbol can be used to construct deterministic matrices satisfying the restricted isometry property.

ADMM-DAD learns an analysis operator associated to a frame, meaning a redundant analysis operator whose associated frame operator is invertible. Frame-based performance conjecture.…

The set $\mathcal{K}_{q,c}$ has Gaussian width $O\big(s\log\frac{n}{s}\big)$ but does not admit a low covering dimension. Conjecture. More advanced concentration inequalities or ge…

Bottleneck conjecture. Moving beyond the $k^2$ bottleneck is likely to require tools beyond the notion of $alpha$-coherence.

For the orthonormal Fourier basis and the orthonormal Haar wavelet basis, the local-coherence estimate used in the paper involves the numerical factor $2700$, through the bound…

In the total variation model, the measurement operator is constructed from four blocks of measurements derived from an operator $\mathcal{A}$, contributing $4m_1$ measurements. Nee…

Let $A\in\{0,1\}^{m\times n}$ be a matrix whose entries are independent and identically distributed Bernoulli $p$ random variables. The robust nullspace property conjecture. There…

The ell1-sparsity condition conjecture. The condition above cannot be improved when ell0-sparsity is replaced by the weaker ell1-sparsity.

Let $\mathbf{x}$ be a $K$-sparse signal, let $\mathbf{y}$ be its noisy measurements, and run OMP for $K$ iterations. Write … for the support-recovery error rate, and let…

Let the box-constrained LASSO detector for spatial modulation with single-symbol transmission use regularization function…

Let $(\mathrm{BP}_{\sigma,\mathcal{K}})$ denote the generalized basis-pursuit program with gauge or structural set $\mathcal{K}$, and let parameter sensitivity refer to the depende…