Compact Lifted Relaxations for Low-Rank Optimization

We study the problem of maximizing a complex-valued quadratic form over the $K^{\text{th}}$ roots of unity. We show that when the objective matrix $\mathbf{Q}^\star \in \mathbb{C}^{n \times n}$ of the quadratic has rank $r$, the global maximizer belongs to a candidate set of size $O(rn^{2r-1})$. This set can be constructed deterministically in $O(rn^{2r+1})$ time by enumerating the vertices of a hyperplane arrangement in $\mathbb{R}^{2r}.$ The algorithm is embarrassingly parallel; with~$P$ processors, the time complexity drops to $O(r n^{2r+1}/P)$. For approximately low-rank settings, where the objective matrix is a noise-perturbed variant of a rank-$r$ matrix, we prove that applying our framework to a spectral truncation yields a multiplicative $(1 - O(\left\|\mathbf{H}\right\|_2 / δ^{\star}))$-approximation guarantee, where $δ^{\star}$ denotes the eigengap of the underlying rank-$r$ matrix and $\mathbf{H}$ represents the perturbation. To scale to high-dimensional problems, we establish a randomized sampling variant. We prove that uniformly sampling $S \geq O(1/\varepsilon^{r-1})$ candidates achieves a $(1-\varepsilon)\cos^2(π/ K)$-approximation of the optimal rank-$r$ solution with high probability. Crucially, this sample size is entirely independent of $n$, reducing the overall runtime to $O(S \cdot n^2)$. Computational experiments on synthetic benchmarks and large-scale graphs for Max-3-Cut confirm that our algorithms match or exceed semi-definite programming solution quality on structured instances while enabling massive parallelization across heterogeneous hardware and scaling seamlessly to problems where $n \geq 10^6$.

We study nonconvex methods for matrix completion, the problem of recovering a low-rank matrix from a subset of its entries. Convex methods achieve sample complexity linear in the matrix dimension and the rank, up to logarithmic factors, whereas global guarantees for commonly used nonconvex methods require a higher polynomial dependence on the rank. We close this gap by analyzing Riemannian gradient descent (RGD) and Riemannian Gauss--Newton (RGN) methods. For an $n\times n$ matrix of rank $r$ with incoherence parameter $μ$ and condition number $κ$, the two methods achieve exact recovery with high probability from $O(μnr\log n\log(nκ))$ and $O(μnr\log n\log(2μrκ))$ observations, respectively. The methods use a multiscale residual initialization, while the analysis simultaneously controls the spectral error and incoherence. The resulting RGD iterates converge linearly, whereas RGN eventually converges Q-quadratically.

Low-rank matrix optimization is often carried out via the Burer-Monteiro (BM) formulation, but choosing the factorization rank $r$ is delicate and can substantially slow optimization. We propose a unified framework, termed direction-magnitude decomposition (DMD), that decomposes the optimization variable to improve optimization efficiency even when the target rank is unknown. We develop two DMD-based approaches and establish their theoretical advantages on the canonical problem of matrix factorization. The first, overparameterized DMD, uses a rank $r$ larger than necessary and enjoys faster convergence as $r$ increases. The second, recursive DMD, is motivated by the incremental eigenpair learning, or saddle-to-saddle, behavior of overparameterized DMD. It achieves lower memory and computational costs, complementing overparameterized DMD. Both approaches are exponentially faster than gradient descent applied to the BM formulation. Numerical experiments on matrix factorization, sensing, and completion corroborate our theoretical findings and demonstrate the practical effectiveness of DMD.