16 problems

Entropy-based measurement conjecture. For sufficiently large $n$, the linear program referred to as LP exactly recovers $x$ from $nH(k/n)/2$ measurements.

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 $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…

Let $K$ be the number of scatters, let $N_{\mathsf c}$ and $\bar{\mathsf X},\bar{\mathsf Y},\bar{\mathsf Z}$ be the sensing and array parameters, and let $r_{\ell_1}^{\circ}$ denot…

Let $p$ be prime, let $\chi(x)=\left(\frac{x}{p}\right)$ denote the Legendre symbol, and let $\{r_1,\ldots,r_k\}\subseteq\mathbb{Z}_p$. For distinct indices $i,j$, set $a=r_j-r_i$…

Approximation conjecture. For these choices of $f$, the statistical dimension is well approximated by the squared Euclidean distance to the scaled subdifferential:

Restricted-isometry conjecture. If $A$ has restricted 2-isometry property of order $tk$ with

Let $\mathbb H$ be either $\mathbb R$ or $\mathbb C$, let $\mathcal L_r^{\mathbb H}$ denote the relevant class of matrices of rank at most $r$, and let ${\bf M}_{\mathcal A}$ be th…

Consider a linear inverse problem in which an input signal ${\bf x}$, generated by a stationary ergodic source, is estimated from noisy measurements ${\bf y}$ and measurement matri…

Legendre-symbol RIP conjecture. There exists a universal constant $C$ such that for every $\delta>0$, there exist $N_0>0$ and $P_0(N)=O(2^{\operatorname{poly}(N)})$ such that, when…

Minimum-energy active-constraint conjecture. Under this assumption, the optimal solution requires only the constraint corresponding to the node with minimum energy, $E_1$, to be ac…

Let $\vct{x}_0\in\mathbb{R}^d$ be the target vector, let $R_{\mathrm{mm}}(\vct{x}_0)$ denote the minimax mean-square-error risk, and consider recovery by the convex program with me…

Let $x\in\mathbb{R}^N$ be the signal, $y=\Phi x+z$ the measurement vector, and $x^U_{MAP}$ the universal MAP estimator. Assume that $\Phi\in\mathbb{R}^{M\times N}$ is an i.i.d. Gau…

Fix $N$ and $M$. Let $\boldsymbol{a} \in \mathbb{R}^N$ be a random $K$-sparse vector whose $K$ nonzero entries, on an arbitrary support $S$, are independent and identically distrib…

Optimal sampling bound conjecture. A random subset $\Omega\subset\{0,1,\ldots,n-1\}$ of average cardinality

Let $\boldsymbol{Q}$ be the capacity matrix, let $\boldsymbol{Q}^{V}$ be the vector of values $Q_{i,j}$ with $i<j$ in $\Omega$, and let $E_Q$ and $\sigma_Q^2$ denote its mean and v…