Low-Rank Plus Sparse Decompositions of Large-Scale Matrices via Semidefinite Optimization

We study the problem of decomposing a symmetric matrix into the sum of a low-rank symmetric positive semidefinite matrix and a tridiagonal matrix, and a relaxation which looks for symmetric positive semidefinite matrices with small nuclear norms. These problems are generalizations of
\nthe problem of decomposing a symmetric matrix into a low-rank symmetric positive semidefinite
\nmatrix plus a diagonal matrix and one of its relaxations, the minimum trace factor analysis problem. We also show that for the relaxation of the low-rank plus tridiagonal decomposition problem
\nwith regularizations on the tridiagonal matrix, the optimal solution is unique when the nonnegative
\nregularizing coefficient is not 2. Then, given such a coefficient λ ∈ R+ \\ {2}, we consider three
\nproblems. The first problem is decomposing a matrix into a low-rank symmetric positive semidefi-
\nnite matrix and a tridiagonal matrix. The second is to determine the facial structure of E′
\nn, which is
\nthe set of correlation matrices whose absolute values of entries right below and above the diagonal
\nentries are upper bounded by λ/2. And the third problem is that given strictly positive integers k, n
\nwith n > k, and points v1, . . . , vn ∈ Rk, determine if there exists a centered (degenerate) ellipsoid
\npassing through all these points exactly such that when the points are projected onto the unit ball
\ncorresponding to the ellipsoid, for every i, the cosine value of the angle between the projected ith
\nand (i + 1)th points is upper bounded by λ/2 and lower bounded by −λ/2. We then prove that all
\nthese three problems are equivalent and when the regularization coefficient λ goes to infinity, we
\nshow the equivalence between them and the corresponding properties of the low-rank plus diagonal
\ndecomposition problem.
\nWe also provide a sufficient condition on a subspace U for us to find a nonempty face of
\nE′
\nn defined by U. By the equivalence above, this is also a sufficient condition for the other two
\nproblems.
\nAfter that, we prove that the low-rank plus tridiagonal problem can be solved in polynomial time when the rank of the positive semidefinite matrix in the decomposition is bounded above by
\nan absolute constant.
\nIn the end, we consider representing our problem as a conic programming problem and generalizing it to general sparsity patterns.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.