Matrix completion via minimizing an approximate rank

Xueying Zeng, Lixin Shen, Yuesheng Xu, Jian Lu

Research output: Contribution to journalArticle

Abstract

The low rank matrix completion problem which aims to recover a matrix from that having missing entries has received much attention in many fields such as image processing and machine learning. The rank of a matrix may be measured by the ℓ0 norm of the vector of its singular values. Due to the nonconvexity and discontinuity of the ℓ0 norm, solving the low rank matrix completion problem which is clearly NP hard suffers from computational challenges. In this paper, we propose a constrained matrix completion model in which a novel nonconvex continuous rank surrogate is used to approximate the rank function of a matrix, promote low rank of the recovered matrix and address the computational challenges. The proposed rank surrogate differs from the convex nuclear norm and other existing state-of-the-art nonconvex surrogates in a way that it alleviates the discontinuity and nonconvexity of the rank function through a local ℓ2-relaxation of the ℓ0 norm so that it possesses several desirable properties. These properties ensure that it accurately approximates the rank function by choosing an appropriate relaxation parameter. We moreover develop an efficient iterative algorithm to solve the resulting model. We also propose strategies of automatically updating the relaxation parameter to practically ensure the global convergence and speed up the algorithm. We establish theoretical convergence results for the proposed algorithm. Experimental results are presented to demonstrate significant performance improvements of the proposed model and the associated algorithm as compared to state-of-the-art methods in both recoverability and computational efficiency.

Original languageEnglish (US)
JournalAnalysis and Applications
DOIs
StatePublished - Jan 1 2019

Fingerprint

Matrix Completion
Low-rank Matrices
Matrix Completion Problem
Norm
Non-convexity
Discontinuity
Singular Values
Global Convergence
Computational Efficiency
Convergence Results
Iterative Algorithm
Updating
Image Processing
Machine Learning
Speedup
Efficient Algorithms
NP-complete problem
Computational efficiency
Model
Rank of a matrix

Keywords

  • Low rank matrices
  • matrix completion
  • singular value decomposition

ASJC Scopus subject areas

  • Analysis
  • Applied Mathematics

Cite this

Matrix completion via minimizing an approximate rank. / Zeng, Xueying; Shen, Lixin; Xu, Yuesheng; Lu, Jian.

In: Analysis and Applications, 01.01.2019.

Research output: Contribution to journalArticle

@article{e50e726104b3462db732f7483d1f4bb9,
title = "Matrix completion via minimizing an approximate rank",
abstract = "The low rank matrix completion problem which aims to recover a matrix from that having missing entries has received much attention in many fields such as image processing and machine learning. The rank of a matrix may be measured by the ℓ0 norm of the vector of its singular values. Due to the nonconvexity and discontinuity of the ℓ0 norm, solving the low rank matrix completion problem which is clearly NP hard suffers from computational challenges. In this paper, we propose a constrained matrix completion model in which a novel nonconvex continuous rank surrogate is used to approximate the rank function of a matrix, promote low rank of the recovered matrix and address the computational challenges. The proposed rank surrogate differs from the convex nuclear norm and other existing state-of-the-art nonconvex surrogates in a way that it alleviates the discontinuity and nonconvexity of the rank function through a local ℓ2-relaxation of the ℓ0 norm so that it possesses several desirable properties. These properties ensure that it accurately approximates the rank function by choosing an appropriate relaxation parameter. We moreover develop an efficient iterative algorithm to solve the resulting model. We also propose strategies of automatically updating the relaxation parameter to practically ensure the global convergence and speed up the algorithm. We establish theoretical convergence results for the proposed algorithm. Experimental results are presented to demonstrate significant performance improvements of the proposed model and the associated algorithm as compared to state-of-the-art methods in both recoverability and computational efficiency.",
keywords = "Low rank matrices, matrix completion, singular value decomposition",
author = "Xueying Zeng and Lixin Shen and Yuesheng Xu and Jian Lu",
year = "2019",
month = "1",
day = "1",
doi = "10.1142/S0219530519400025",
language = "English (US)",
journal = "Analysis and Applications",
issn = "0219-5305",
publisher = "World Scientific Publishing Co. Pte Ltd",

}

TY - JOUR

T1 - Matrix completion via minimizing an approximate rank

AU - Zeng, Xueying

AU - Shen, Lixin

AU - Xu, Yuesheng

AU - Lu, Jian

PY - 2019/1/1

Y1 - 2019/1/1

N2 - The low rank matrix completion problem which aims to recover a matrix from that having missing entries has received much attention in many fields such as image processing and machine learning. The rank of a matrix may be measured by the ℓ0 norm of the vector of its singular values. Due to the nonconvexity and discontinuity of the ℓ0 norm, solving the low rank matrix completion problem which is clearly NP hard suffers from computational challenges. In this paper, we propose a constrained matrix completion model in which a novel nonconvex continuous rank surrogate is used to approximate the rank function of a matrix, promote low rank of the recovered matrix and address the computational challenges. The proposed rank surrogate differs from the convex nuclear norm and other existing state-of-the-art nonconvex surrogates in a way that it alleviates the discontinuity and nonconvexity of the rank function through a local ℓ2-relaxation of the ℓ0 norm so that it possesses several desirable properties. These properties ensure that it accurately approximates the rank function by choosing an appropriate relaxation parameter. We moreover develop an efficient iterative algorithm to solve the resulting model. We also propose strategies of automatically updating the relaxation parameter to practically ensure the global convergence and speed up the algorithm. We establish theoretical convergence results for the proposed algorithm. Experimental results are presented to demonstrate significant performance improvements of the proposed model and the associated algorithm as compared to state-of-the-art methods in both recoverability and computational efficiency.

AB - The low rank matrix completion problem which aims to recover a matrix from that having missing entries has received much attention in many fields such as image processing and machine learning. The rank of a matrix may be measured by the ℓ0 norm of the vector of its singular values. Due to the nonconvexity and discontinuity of the ℓ0 norm, solving the low rank matrix completion problem which is clearly NP hard suffers from computational challenges. In this paper, we propose a constrained matrix completion model in which a novel nonconvex continuous rank surrogate is used to approximate the rank function of a matrix, promote low rank of the recovered matrix and address the computational challenges. The proposed rank surrogate differs from the convex nuclear norm and other existing state-of-the-art nonconvex surrogates in a way that it alleviates the discontinuity and nonconvexity of the rank function through a local ℓ2-relaxation of the ℓ0 norm so that it possesses several desirable properties. These properties ensure that it accurately approximates the rank function by choosing an appropriate relaxation parameter. We moreover develop an efficient iterative algorithm to solve the resulting model. We also propose strategies of automatically updating the relaxation parameter to practically ensure the global convergence and speed up the algorithm. We establish theoretical convergence results for the proposed algorithm. Experimental results are presented to demonstrate significant performance improvements of the proposed model and the associated algorithm as compared to state-of-the-art methods in both recoverability and computational efficiency.

KW - Low rank matrices

KW - matrix completion

KW - singular value decomposition

UR - http://www.scopus.com/inward/record.url?scp=85069841383&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85069841383&partnerID=8YFLogxK

U2 - 10.1142/S0219530519400025

DO - 10.1142/S0219530519400025

M3 - Article

AN - SCOPUS:85069841383

JO - Analysis and Applications

JF - Analysis and Applications

SN - 0219-5305

ER -