A Caltech Library Service

Recovering Structured Low-rank Operators Using Nuclear Norms


Bruer, John Jacob (2017) Recovering Structured Low-rank Operators Using Nuclear Norms. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z9F18WQS.


This work considers the problem of recovering matrices and operators from limited and/or noisy observations. Whereas matrices result from summing tensor products of vectors, operators result from summing tensor products of matrices. These constructions lead to viewing both matrices and operators as the sum of "simple" rank-1 factors.

A popular line of work in this direction is low-rank matrix recovery, i.e., using linear measurements of a matrix to reconstruct it as the sum of few rank-1 factors. Rank minimization problems are hard in general, and a popular approach to avoid them is convex relaxation. Using the trace norm as a surrogate for rank, the low-rank matrix recovery problem becomes convex.

While the trace norm has received much attention in the literature, other convexifications are possible. This thesis focuses on the class of nuclear norms—a class that includes the trace norm itself. Much as the trace norm is a convex surrogate for the matrix rank, other nuclear norms provide convex complexity measures for additional matrix structure. Namely, nuclear norms measure the structure of the factors used to construct the matrix.

Transitioning to the operator framework allows for novel uses of nuclear norms in recovering these structured matrices. In particular, this thesis shows how to lift structured matrix factorization problems to rank-1 operator recovery problems. This new viewpoint allows nuclear norms to measure richer types of structures present in matrix factorizations.

This work also includes a Python software package to model and solve structured operator recovery problems. Systematic numerical experiments in operator denoising demonstrate the effectiveness of nuclear norms in recovering structured operators. In particular, choosing a specific nuclear norm that corresponds to the underlying factor structure of the operator improves the performance of the recovery procedures when compared, for instance, to the trace norm. Applications in hyperspectral imaging and self-calibration demonstrate the additional flexibility gained by utilizing operator (as opposed to matrix) factorization models.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:matrix factorization;operator factorization;nuclear norms;convex optimization;denoising;self-calibration
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Applied And Computational Mathematics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Tropp, Joel A.
Thesis Committee:
  • Tropp, Joel A. (chair)
  • Hassibi, Babak
  • Wierman, Adam C.
  • Yue, Yisong
Defense Date:17 January 2017
Funding AgencyGrant Number
Moore FoundationUNSPECIFIED
Sloan Research FellowshipUNSPECIFIED
Record Number:CaltechTHESIS:02082017-062956314
Persistent URL:
Related URLs:
URLURL TypeDescription ItemGithub page for operfact Python package
Bruer, John Jacob0000-0003-4590-3038
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10048
Deposited By: John Bruer
Deposited On:13 Feb 2017 20:09
Last Modified:04 Oct 2019 00:15

Thesis Files

PDF (Complete thesis) - Final Version
See Usage Policy.

[img] Archive (ZIP) (Operfact Python Package) - Supplemental Material
See Usage Policy.

[img] Archive (ZIP) (Computer code for numerical experiments) - Supplemental Material
See Usage Policy.


Repository Staff Only: item control page