Back to search

University of Waterloo

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

Abstract

dc:description.abstract

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 the problem of decomposing a symmetric matrix into a low-rank symmetric positive semidefinite matrix 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 with regularizations on the tridiagonal matrix, the optimal solution is unique when the nonnegative regularizing coefficient is not 2. Then, given such a coefficient λ ∈ R+ \ {2}, we consider three problems. The first problem is decomposing a matrix into a low-rank symmetric positive semidefi- nite matrix and a tridiagonal matrix. The second is to determine the facial structure of E′ n, which is the set of correlation matrices whose absolute values of entries right below and above the diagonal entries are upper bounded by λ/2. And the third problem is that given strictly positive integers k, n with n > k, and points v1, . . . , vn ∈ Rk, determine if there exists a centered (degenerate) ellipsoid passing through all these points exactly such that when the points are projected onto the unit ball corresponding to the ellipsoid, for every i, the cosine value of the angle between the projected ith and (i + 1)th points is upper bounded by λ/2 and lower bounded by −λ/2. We then prove that all these three problems are equivalent and when the regularization coefficient λ goes to infinity, we show the equivalence between them and the corresponding properties of the low-rank plus diagonal decomposition problem. We also provide a sufficient condition on a subspace U for us to find a nonempty face of E′ n defined by U. By the equivalence above, this is also a sufficient condition for the other two problems. After 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 an absolute constant. In the end, we consider representing our problem as a conic programming problem and generalizing it to general sparsity patterns.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gong, Rui
Advisor dc:contributor.advisor
  • Tuncel, Levent

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/19463

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gong, Rui. Low-Rank Plus Sparse Decompositions of Large-Scale Matrices via Semidefinite Optimization. University of Waterloo, 2023. http://hdl.handle.net/10012/19463