2018/02/14 by Jirong Yi, Yi, Jirong, Weiyu Xu +1
Computer Science · Engineering · Mathematics · #Advanced SAR Imaging Techniques #Blind Source Separation Techniques #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Signal Processing (eess.SP) #Sparse and Compressive Sensing Techniques #cs.IT #cs.LG #eess.SP #electronic engineering #information engineering #math.IT #math.OC #stat.ML
paper · pdf · doi:10.48550/arxiv.1802.05234
17 pages, 0 figures
arxiv created 2018/02/14 · openalex publication_date 2018/02/14 · arxiv updated 2018/02/15 · openalex created_date 2018/02/23 · openalex updated_date 2026/07/28
Low-rank matrix recovery has found many applications in science and engineering such as machine learning, signal processing, collaborative filtering, system identification, and Euclidean embedding. But the low-rank matrix recovery problem is an NP hard problem and thus challenging. A commonly used heuristic approach is the nuclear norm minimization. In [12,14,15], the 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). In addition, in [12], 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 in [12] is only a sufficient condition for successful matrix recovery using nuclear norm minimization, and is not a necessary condition as claimed in [12]. In this paper, 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.