10 problems

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…

Let the sample matrices be … where $\mathbf{\xi}_k$ are independent copies of a random vector $\mathbf{\xi}$ whose entries are i.i.d. copies of a subgaussian random variable $\xi$…

Sub-gradient identification conjecture. The true solutions identified by the sub-gradient method applied to the $\ell_1$-loss might be non-active strict saddle points.

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

Non-active true-solution conjecture. A subset of the true solutions are non-active strict saddle points.

Local-search convergence conjecture. The conditions required for local-search algorithms to converge to the true solutions may be considerably less stringent than the conditions re…

Non-active strict-saddle conjecture. In situations where the true solutions are neither local nor global minima, they may nevertheless manifest as non-active strict saddle points.

Let $X_\sharp\in\mathbb{R}^{d\times r}$ be a rank-$r$ matrix, let $\mathcal{X}$ denote the feasible region, and set … Here $\operatorname{dist}_{\|\cdot\|_{2,1}}$ denotes distance…

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…

Let $m$ be the number of measurements used to recover $n\times n$ matrices of rank $r$ by rank minimization. The strong recovery requirement from Theorem 1 is $m\geq 4nr-4r^2$. Str…