CaltechTHESIS
  A Caltech Library Service

Recovering Structured Low-rank Operators Using Nuclear Norms

Citation

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

Abstract

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
Funders:
Funding AgencyGrant Number
Moore FoundationUNSPECIFIED
ONRN00014-11-1002
AFOSRFA9550-09-1-0643
Sloan Research FellowshipUNSPECIFIED
Record Number:CaltechTHESIS:02082017-062956314
Persistent URL:http://resolver.caltech.edu/CaltechTHESIS:02082017-062956314
DOI:10.7907/Z9F18WQS
Related URLs:
URLURL TypeDescription
https://github.com/jbruer/operfactRelated ItemGithub page for operfact Python package
ORCID:
AuthorORCID
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
Collection:CaltechTHESIS
Deposited By: John Bruer
Deposited On:13 Feb 2017 20:09
Last Modified:16 Jun 2017 22:19

Thesis Files

[img]
Preview
PDF (Complete thesis) - Final Version
See Usage Policy.

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

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

39Kb

Repository Staff Only: item control page