2011/12/11 by B. Mishra, Bamdev Mishra, G. Meyer +9 · 6 citations
Computer Science · Engineering · Mathematics · #Advanced Image Processing Techniques #Advanced Vision and Imaging #Applied mathematics #Combinatorics #Computer science #Eigenvalues and eigenvectors #FOS: Computer and information sciences #FOS: Mathematics #Hessian matrix #Low-rank approximation #Machine Learning (cs.LG) #Mathematical optimization #Mathematics #Matrix norm #Norm (philosophy) #Optimization and Control (math.OC) #Optimization problem #Rank (graph theory) #Rate of convergence #Sparse and Compressive Sensing Techniques #Tensor (intrinsic definition) #cs.LG #math.OC
paper · pdf · doi:10.48550/arxiv.1112.2318
published in arXiv (Cornell University) (Cornell University) · Submitted
openalex publication_date 2011/12/11 · arxiv created 2013/06/03 · arxiv updated 2013/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The paper addresses the problem of low-rank trace norm minimization. We propose an algorithm that alternates between fixed-rank optimization and rank-one updates. The fixed-rank optimization is characterized by an efficient factorization that makes the trace norm differentiable in the search space and the computation of duality gap numerically tractable. The search space is nonlinear but is equipped with a particular Riemannian structure that leads to efficient computations. We present a second-order trust-region algorithm with a guaranteed quadratic rate of convergence. Overall, the proposed optimization scheme converges super-linearly to the global solution while maintaining complexity that is linear in the number of rows and columns of the matrix. To compute a set of solutions efficiently for a grid of regularization parameters we propose a predictor-corrector approach that outperforms the naive warm-restart approach on the fixed-rank quotient manifold. The performance of the proposed algorithm is illustrated on problems of low-rank matrix completion and multivariate linear regression.