17 problems

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…

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

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

Let $A$ be a finite set with additive energy satisfying … Suppose there are subsets $A',B'\subseteq A$ with … and … where $c_2,c_3,c_4>0$ are constants. Optimal exponent conjecture…

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

Let $K$ be the sparsity level and let $\boldsymbol{A}$ be a sensing matrix whose RIP constant of order $K+1$ is $\delta_{K+1}$. Orthogonal least squares (OLS) is considered for rec…

Let the columnwise Khatri–Rao product be formed from two $m\times n$ subgaussian matrices, and let $k$ denote the order of the restricted isometry property. Khatri–Rao product conj…

Let $\mathbf \Phi\in\mathbb H^{m\times n}$ satisfy the $2s$-restricted isometry property with constant $\delta_{2s}$, and consider stable reconstruction by $\ell_1$-norm minimizati…

Dai and Mo's conjecture. There exist a matrix $\boldsymbol{A}$ with

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…

Complete derandomization conjecture. No random bits are necessary for the Legendre-symbol-based construction; equivalently, the construction should satisfy the required restricted…

Let $\Phi$ be an $M\times N$ sensing matrix, and let $K$ be a sparsity level. The $(K,\delta)$-restricted isometry property (RIP) requires … for every vector $x$ with at most $K$ n…

An equiangular tight frame (ETF) is a collection of vectors with equal pairwise inner-product magnitudes that forms a tight frame. For a matrix, the $(K,\delta)$-restricted isometr…

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

Let $s$ denote the sparsity level, let $\bar{k}$ denote the relevant support-size parameter, and let $\rho_+(\bar{k})$ and $\rho_-(s)$ be the corresponding upper and lower restrict…