Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization

2019/11/11 by Ting Tao, Tao, Ting, Shaohua Pan +3 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced SAR Imaging Techniques #Algorithm #Applied mathematics #Combinatorics #Exponent #FOS: Computer and information sciences #FOS: Mathematics #Factorization #Hessian matrix #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical analysis #Mathematics #Mean squared error #Norm (philosophy) #Numerical methods in inverse problems #Optimization and Control (math.OC) #Rank (graph theory) #Sparse and Compressive Sensing Techniques #Statistics #Upper and lower bounds #cs.LG #math.OC #stat.ML

paper · pdf · doi:10.48550/arxiv.1911.04293

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2019/11/11 · openalex created_date 2019/11/22 · arxiv created 2021/06/26 · arxiv updated 2021/06/29 · openalex updated_date 2026/08/06

Abstract

This paper is concerned with the squared F(robenius)-norm regularized factorization form for noisy low-rank matrix recovery problems. Under a suitable assumption on the restricted condition number of the Hessian for the loss function, we derive an error bound to the true matrix for the non-strict critical points with rank not more than that of the true matrix. Then, for the squared F-norm regularized factorized least squares loss function, under the noisy and full sample setting we establish its KL property of exponent 1/2 on its global minimizer set, and under the noisy and partial sample setting achieve this property for a class of critical points. These theoretical findings are also confirmed by solving the squared F-norm regularized factorization problem with an accelerated alternating minimization method.

Citations

• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Matrix Completion has No Spurious Local Minimum
• Global Optimality of Local Search for Low Rank Matrix Recovery
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• The Global Optimization Geometry of Low-Rank Matrix Optimization
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition

Cited by

• A Complete Loss Landscape Analysis of Regularized Deep Matrix Factorization

Related

• KL property of exponent 1/2 of ℓ_2,0-norm and DC regularized factorizations for low-rank matrix recovery
• Column ℓ_2,0-norm regularized factorization model of low-rank matrix recovery and its computation
• Factor Group-Sparse Regularization for Efficient Low-Rank Matrix Recovery
• RIP-based Performance Guarantee for Low Rank Matrix Recovery via L_*-F Minimization
• On solving a rank regularized minimization problem via equivalent factorized column-sparse regularized models