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

DOI10.1007/S10898-021-01077-0zbMATH Open1490.90283arXiv1911.04293OpenAlexW3198205161MaRDI QIDQ2052408FDOQ2052408

Authors: Ting Tao, Shaohua Pan, Shujun Bi 

Publication date: 26 November 2021

Published in: Journal of Global Optimization (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1911.04293

Recommendations

• KL property of exponent \(1/2\) of \(\ell_{2,0}\)-norm and DC regularized factorizations for low-rank matrix recovery
• Publication:4945779
• Error bound for product quadrature rules in \(L_ 1\)-weighted norm
• Error bounds, quadratic growth, and linear convergence of proximal methods
• Fundamental error estimate inequalities for the Tikhonov regularization using reproducing kernels
• The \({L^2}\) norm error estimate for linear element and its applications
• Optimal error bounds for non-expansive fixed-point iterations in normed spaces
• Error estimates for the regularization of least squares problems
• Error bounds and singularity degree in semidefinite programming
• Sharp 2-norm error bounds for LSQR and the conjugate gradient method

zbMATH Keywords

error boundKL property of exponent 1/2F-norm regularized factorization

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Cites Work

• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Matrix completion and low-rank SVD via fast alternating least squares
• Variational Analysis
• Title not available (Why is that?)
• Exact matrix completion via convex optimization
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Restricted strong convexity and weighted matrix completion: optimal bounds with noise
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Optimal rates of convergence for covariance matrix estimation
• A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
• An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
• Low-rank matrix completion using alternating minimization
• Log-concavity and strong log-concavity: a review
• Guaranteed Matrix Completion via Non-Convex Factorization
• Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• CoCoLasso for high-dimensional error-in-variables regression
• Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
• The non-convex geometry of low-rank matrix optimization
• First-order methods almost always avoid strict saddle points
• Global Optimality in Low-Rank Matrix Optimization
• The Global Optimization Geometry of Low-Rank Matrix Optimization

Cited In (2)

• Column \(\ell_{2,0}\)-norm regularized factorization model of low-rank matrix recovery and its computation
• KL property of exponent \(1/2\) of \(\ell_{2,0}\)-norm and DC regularized factorizations for low-rank matrix recovery

This page was built for publication: Error bound of critical points and KL property of exponent 1/2 for squared F-norm regularized factorization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052408)