Necessary and Sufficient Null Space Condition for Nuclear Norm Minimization in Low-Rank Matrix Recovery

Jirong Yi; Weiyu Xu

doi:10.1109/TIT.2020.2990948

Back

Necessary and Sufficient Null Space Condition for Nuclear Norm Minimization in Low-Rank Matrix Recovery

Journal article

Open access

Peer reviewed

Necessary and Sufficient Null Space Condition for Nuclear Norm Minimization in Low-Rank Matrix Recovery

Jirong Yi and Weiyu Xu

IEEE transactions on information theory, Vol.66(10), pp.6597-6604

10/2020

DOI: 10.1109/TIT.2020.2990948

Files and links (1)

url

https://doi.org/10.1109/TIT.2020.2990948View

Published (Version of record) Open Access

Abstract

Low-rank matrix recovery has found many applications in science and engineering such as machine learning, system identification, and Euclidean embedding. However, the low-rank matrix recovery problem is an NP hard problem and thus challenging. A commonly used heuristic approach is the nuclear norm minimization. Recently, some authors established the necessary and sufficient null space conditions for nuclear norm minimization to recover every possible low-rank matrix with rank at most r (the strong null space condition). Oymak et al. established a null space condition for successful recovery of a given low-rank matrix (the weak null space condition) using nuclear norm minimization, and derived the phase transition for the nuclear norm minimization. In this paper, we show that the weak null space condition proposed by Oymak et al. is only a sufficient condition for successful matrix recovery using nuclear norm minimization, and is not a necessary condition as claimed. We further give a weak null space condition for low-rank matrix recovery, which is both necessary and sufficient for the success of nuclear norm minimization. At the core of our derivation are an inequality for characterizing the nuclear norms of block matrices, and the conditions for equality to hold in that inequality.

block matrices

dual norm

Eigenvalues and eigenfunctions

Linear matrix inequalities

Matrix decomposition

matrix recovery

Minimization

nuclear norm minimization

Null space

Null space condition

Singular value decomposition

Sparse matrices

Details

Title: Subtitle: Necessary and Sufficient Null Space Condition for Nuclear Norm Minimization in Low-Rank Matrix Recovery
Creators: Jirong Yi - University of Iowa
Weiyu Xu - University of Iowa
Resource Type: Journal article
Publication Details: IEEE transactions on information theory, Vol.66(10), pp.6597-6604
Publisher: IEEE
DOI: 10.1109/TIT.2020.2990948
ISSN: 0018-9448
eISSN: 1557-9654
Grant note: 318608 / Simons Foundation (10.13039/100000893) DMS-1418737 / NSF (10.13039/100000001)
Language: English
Date published: 10/2020
Academic Unit: Electrical and Computer Engineering
Record Identifier: 9984197343802771

Metrics

9 Record Views

6 Times Cited - Web of Science