33 problems

Let a partial matrix have a bipartite graph whose vertices represent its rows and columns and whose edges represent specified entries. A fully specified submatrix is one in which e…

Let $\mathcal{T}$ be a tensor whose mode-1 unfolding $\mathcal{T}_{(1)}$ is observed on $\Omega_{\mathcal{T}}$, let $M$ be a matrix observed on $\Omega_M$, and let $G$ be the unkno…

GM-MDS conjecture. The MDS condition is sufficient, as well as necessary, to guarantee the existence of an MDS generator matrix over any field of size linear in the length of the c…

Smaller-extension-degree conjecture. The construction is MDP also for smaller values of $d$. The conjecture would reduce the finite-field extension degree needed by this matrix-com…

Let $A$ be the observed matrix associated with a tensor-completion problem, let $M$ denote the underlying signal matrix, and let $B$ be the matrix whose eigenvectors are embedded i…

Rank-imbalance conjecture. Highly rank-imbalanced true solutions are unlikely to emerge as local minima of the loss function.

Let $\boldsymbol{\Omega}$ denote the matrix of observation indicators, with entries $omega_{ij}$ uniformly sampled, and let $hat{\mathbf A}$ be the matrix produced in Step 2 of Met…

Let $\mathcal{V}^{\ominus}$ be the set of vectors under consideration, and let $\prec$ denote the majorization order. For arbitrary $\bm u,\bm v\in\mathcal{V}^{\ominus}$, Common ma…

Sufficiency conjecture. The upper bound of Lemma should suffice to invoke the cited matrix-completion result, although with larger residual terms and a lower probability of success…

Fixed-weight-matrix conjecture. There exists a large constant $\Gamma(\epsilon)>0$ such that every instance $\mathcal{MC}(C,u^*)$ satisfying

Complexity-metric landscape conjecture. There exist constants $\delta,\Delta>0$ such that: (1) if $\mathbb{D}_\alpha(C,u^*)\leq\delta\mu n/\alpha$, then $\mathcal{MC}(C,u^*)$ has n…

Threshold conjecture. The instance $\mathcal{MC}(C^\epsilon,u^*)$ has spurious solutions if $\epsilon < (m+1)^{-1} + o(m^{-1})$ and does not have spurious solutions if…

Let $\bm H_n=\bm W_{pq}^{n}(\bm W_{pq}^{n})^{\top}$ be the matrix from Theorem, where $\bm W_q^n=\bm V_{\perp}^{n_2}\otimes\bm U_{\perp}^{n_1}$ forms a concentrated sequence of sem…

The authors' conjecture. The proposed multi-step reweighted convex penalization approach and convolution smoothing will lead to oracle statistical guarantees and fast computational…

Let $f$ denote the true data-generating function, and let $\widehat{f}$ be the estimate produced by the modified USVT estimator. Under a model that is correct, compare this estimat…

Let ${\cal M}$ be a pattern matrix under the paper's standing Assumption, and let $k\geq 1$. The problem $\operatorname{GLRMC}({\cal M},k)$ asks whether, for almost all values of t…

Let $K_n$ be the complete graph. The $d$-hyperconnectivity matroid $\mathcal H_n^d$ is a $\{K_{d+2},K_{d+1,d+1}\}$-matroid, $\mathcal I_n^2$ is a $\{K_5,K_{3,3}\}$-matroid, and…

Finite-completion conjecture. Without loss of generality, let the number of $1$'s at every row and column of $\Omega$ be at least $r+1$. Then a generic rank-$r$ matrix $X$ observed…

Let $G$ be a full-rank typical graph. A $G$-partial matrix is a partial symmetric matrix whose specified off-diagonal entries correspond to the edges of $G$; it is minimally comple…

Let $\operatorname{LS}_n(r,s)$ denote the set of matrices that can be written as the sum of an $n\times n$ matrix of rank at most $r$ and an $n\times n$ matrix with at most $s$ non…

Let $M^*\in\mathcal{S}^{d\times d}$ be symmetric positive semidefinite, and let $\Omega$ be generated under the model $\operatorname{SMC}(M^*,p)$: each $(i,j)$ with $i\geq j$ is ob…

Bipartite circulant generic-rank conjecture. Every graph $G(n,l)$ has generic completion rank predicted by the dimension count; equivalently,

3-core conjecture. The maximal typical rank of $G$ is at least $3$.

G(8,6) typical-rank conjecture. The graph $G(8,6)$ exhibits three typical ranks.

Toeplitz completion conjecture. Whenever a partially positive definite Toeplitz matrix with pattern $P_3$ is positive definite completable, it admits a Toeplitz completion.