matrix completion

Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition

  • Ching-pei Lee
  • Ling Liang
  • Tianyun Tang
  • Kim-Chuan Toh
    • Categories Global Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    This work proposes a rapid algorithm, BM-Global, for nuclear-norm-regularized convex and low-rank matrix optimization problems. BM-Global efficiently decreases the objective value via low-cost steps leveraging the nonconvex but smooth Burer-Monteiro (BM) decomposition, while effectively escapes saddle points and spurious local minima ubiquitous in the BM form to obtain guarantees of fast convergence rates to the … Read more

    An Inertial Block Majorization Minimization Framework for Nonsmooth Nonconvex Optimization

  • Nicolas Gillis
  • Le Thi Khanh Hien
  • Duy Nhat Phan
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    In this paper, we introduce TITAN, a novel inerTial block majorIzation minimization framework for non-smooth non-convex opTimizAtioN problems. TITAN is a block coordinate method (BCM) that embeds inertial force to each majorization-minimization step of the block updates. The inertial force is obtained via an extrapolation operator that subsumes heavy-ball and Nesterov-type accelerations for block proximal … Read more

    Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories Cutting Plane Approaches, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , ,

    We propose a framework for modeling and solving low-rank optimization problems to certifiable optimality. We introduce symmetric projection matrices that satisfy $Y^2 = Y$, the matrix analog of binary variables that satisfy $z^2 = z$, to model rank constraints. By leveraging regularization and strong duality, we prove that this modeling paradigm yields tractable convex optimization … Read more

    Beyond Alternating Updates for Matrix Factorization with Inertial Bregman Proximal Gradient Algorithms

  • Mahesh Chandra Mukkamala
  • Peter Ochs
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , , ,

    Matrix Factorization is a popular non-convex objective, for which alternating minimization schemes are mostly used. They usually suffer from the major drawback that the solution is biased towards one of the optimization variables. A remedy is non-alternating schemes. However, due to a lack of Lipschitz continuity of the gradient in matrix factorization problems, convergence cannot … Read more

    A Unified Framework for Sparse Relaxed Regularized Regression: SR3

  • Aleksandr Y. Aravkin
  • Peng Zheng
  • Travis Askham
  • Steve Brunton
  • Nathan Kutz
    • Categories Nonlinear Systems and Least-Squares, Nonsmooth Optimization, Statistics Tags , , , ,

    Regularized regression problems are ubiquitous in statistical modeling, signal processing, and machine learning. Sparse regression in particular has been instrumental in scientific model discovery, including compressed sensing applications, vari- able selection, and high-dimensional analysis. We propose a broad framework for sparse relaxed regularized regression, called SR3. The key idea is to solve a relaxation of … Read more

    An Alternating Minimization Method for Matrix Completion Problem

  • Xin Liu
  • Yuan Shen
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , ,

    In this paper, we focus on solving matrix completion problem arising from applications in the fields of information theory, statistics, engineering, etc. However, the matrix completion problem involves nonconvex rank constraints which make this type of problem difficult to handle. Traditional approaches use a nuclear norm surrogate to replace the rank constraints. The relaxed model … Read more

    Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation

  • Bo Jiang
  • Shiqian Ma
  • Anthony Man-Cho So
  • Shuzhong Zhang
    • Categories Constrained Nonlinear Optimization, Stochastic Programming Tags , , , ,

    In this paper, we propose a vector transport-free stochastic variance reduced gradient (SVRG) method with general retraction for empirical risk minimization over Riemannian manifold. Existing SVRG methods on manifold usually consider a specific retraction operation, and involve additional computational costs such as parallel transport or vector transport. The vector transport-free SVRG with general retraction we … Read more

    Open research areas in distance geometry

  • Carlile Lavor
  • Leo Liberti
    • Categories Basic Sciences Applications, Data-Mining, Global Optimization Applications Tags , , , ,

    Distance Geometry is based on the inverse problem that asks to find the positions of points, in a Euclidean space of given dimension, that are compatible with a given set of distances. We briefly introduce the field, and discuss some open and promising research areas. Article Download View Open research areas in distance geometry

    Max-Norm Optimization for Robust Matrix Recovery

  • Ethan Fang
  • Kim-Chuan Toh
  • Han Liu
  • Wen-Xin Zhou
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , ,

    This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform … Read more

    An Extended Frank-Wolfe Method with “In-Face” Directions, and its Application to Low-Rank Matrix Completion

  • Robert M. Freund
  • Rahul Mazumder
  • Paul Grigas
    • Categories Convex Optimization, Data-Mining Tags , , , , ,

    We present an extension of the Frank-Wolfe method that is designed to induce near-optimal solutions on low-dimensional faces of the feasible region. We present computational guarantees for the method that trade off efficiency in computing near-optimal solutions with upper bounds on the dimension of minimal faces of iterates. We apply our method to the low-rank … Read more