Low-rank matrix completion using nuclear norm minimization and facial reduction

Shimeng Huang and Henry Wolkowicz ()
Additional contact information
Shimeng Huang: University of Waterloo
Henry Wolkowicz: University of Waterloo

Journal of Global Optimization, 2018, vol. 72, issue 1, No 2, 5-26

Abstract: Abstract Minimization of the nuclear norm, NNM, is often used as a surrogate (convex relaxation) for finding the minimum rank completion (recovery) of a partial matrix. The minimum nuclear norm problem can be solved as a trace minimization semidefinite programming problem, SDP. Interior point algorithms are the current methods of choice for this class of problems. This means that it is difficult to: solve large scale problems; exploit sparsity; and get high accuracy solutions. The SDP and its dual are regular in the sense that they both satisfy strict feasibility. In this paper we take advantage of the structure of low rank solutions in the SDP embedding. We show that even though strict feasibility holds, the facial reduction framework used for problems where strict feasibility fails can be successfully applied to generically obtain a proper face that contains all minimum low rank solutions for the original completion problem. This can dramatically reduce the size of the final NNM problem, while simultaneously guaranteeing a low-rank solution. This can be compared to identifying part of the active set in general nonlinear programming problems. In the case that the graph of the sampled matrix has sufficient bicliques, we get a low rank solution independent of any nuclear norm minimization. We include numerical tests for both exact and noisy cases. We illustrate that our approach yields lower ranks and higher accuracy than obtained from just the NNM approach.

Keywords: Low-rank matrix completion; Matrix recovery; Semidefinite programming (SDP); Facial reduction; Bicliques; Slater condition; Nuclear norm; Compressed sensing; 65J22; 90C22; 65K10; 52A41; 90C46 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-017-0590-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:72:y:2018:i:1:d:10.1007_s10898-017-0590-1

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-017-0590-1

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().