Low-rank matrix completion using nuclear norm minimization and facial reduction
From MaRDI portal
Publication:1756746
Abstract: Minimization of the nuclear norm 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). The SDP and its dual are regular in the sense that they both satisfy strict feasibility. Interior point algorithms are the current methods of choice for these problems. This means that it is difficult to solve large scale problems and difficult to get high accuracy solutions. In this paper we take advantage of the structure at optimality for the minimum nuclear norm problem. We show that even though strict feasibility holds, the facial reduction framework can be successfully applied to obtain a proper face that contains the optimal set, and thus can dramatically reduce the size of the final nuclear norm problem while guaranteeing a low-rank solution. We include numerical tests for both exact and noisy cases. In all cases we assume that knowledge of a target rank is available.
Recommendations
- Fixed point and Bregman iterative methods for matrix rank minimization
- An implementable proximal point algorithmic framework for nuclear norm minimization
- An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
- The minimum-rank Gram matrix completion via a fixed point continuation method
- Low-rank matrix recovery via iteratively reweighted least squares minimization
Cites work
- A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming
- CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
- Coordinate shadows of semidefinite and Euclidean distance matrices
- Exact matrix completion via convex optimization
- Explicit sensor network localization using semidefinite representations and facial reductions
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- scientific article; zbMATH DE number 1489799 (Why is no real title available?)
- Learning Theory
- Low rank matrix completion by alternating steepest descent methods
- Max-norm optimization for robust matrix recovery
- Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier
- Randomized Sketches of Convex Programs With Sharp Guarantees
- The algebraic combinatorial approach for low-rank matrix completion
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- Uniqueness of low-rank matrix completion by rigidity theory
Cited in
(6)- Robust principal component analysis using facial reduction
- A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion
- An extended Frank-Wolfe method with ``in-face directions, and its application to low-rank matrix completion
- Linear Time Dynamic Programming for Computing Breakpoints in the Regularization Path of Models Selected From a Finite Set
- An ADMM-factorization algorithm for low rank matrix completion
- An upper bound on the minimum rank of a symmetric Toeplitz matrix completion problem
This page was built for publication: Low-rank matrix completion using nuclear norm minimization and facial reduction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1756746)
