Orthogonal Rank-One Matrix Pursuit for Low Rank Matrix Completion (2014-04-04T00:00:00.000000Z)

TL;DR

An efficient and scalable low rank matrix completion algorithm to extend the orthogonal matching pursuit method from the vector case to the matrix case is proposed and an economic version is proposed by introducing a novel weight updating rule to reduce the time and storage complexity.

Abstract

In this paper, we propose an efficient and scalable low rank matrix completion algorithm. The key idea is to extend the orthogonal matching pursuit method from the vector case to the matrix case. We further propose an economic version of our algorithm by introducing a novel weight updating rule to reduce the time and storage complexity. Both versions are computationally inexpensive for each matrix pursuit iteration and find satisfactory results in a few iterations. Another advantage of our proposed algorithm is that it has only one tunable parameter, which is the rank. It is easy to understand and to use by the user. This becomes especially important in large-scale learning problems. In addition, we rigorously show that both versions achieve a linear convergence rate, which is significantly better than the previous known results. We also empirically compare the proposed algorithms with several state-of-the-art matrix completion algorithms on many real-world datasets, including the large-scale recommendati...

Authors

Jieping Ye

5 papers

Z. Wang

1 papers

M. Lai

1 papers

TL;DR

Abstract

Authors

References54 items

Parallel stochastic gradient algorithms for large-scale matrix completion

Improved Iteratively Reweighted Least Squares for Unconstrained Smoothed 퓁q Minimization

Low-rank matrix completion using alternating minimization

Accelerated Training for Matrix-norm Regularization: A Boosting Approach

Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm

Lifted coordinate descent for learning with trace-norm regularization

Greedy Algorithms for Structurally Constrained High Dimensional Problems

Low-Rank Optimization with Trace Norm Penalty

Large-Scale Convex Minimization with a Low-Rank Constraint

A coordinate gradient descent method for ℓ1-regularized convex minimization

An implementable proximal point algorithmic framework for nuclear norm minimization

Penalty decomposition methods for rank minimization

A Simple Algorithm for Nuclear Norm Regularized Problems

Online identification and tracking of subspaces from highly incomplete information

Spectral Regularization Algorithms for Learning Large Incomplete Matrices

Regularization Paths for Generalized Linear Models via Coordinate Descent.

Estimation of (near) low-rank matrices with noise and high-dimensional scaling

The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition by Trevor Hastie, Robert Tibshirani, Jerome Friedman

Guaranteed Rank Minimization via Singular Value Projection

Matrix Factorization Techniques for Recommender Systems

Stochastic methods for l1 regularized loss minimization

An accelerated gradient method for trace norm minimization

Fixed point and Bregman iterative methods for matrix rank minimization

ADMiRA: Atomic Decomposition for Minimum Rank Approximation

Convex multi-task feature learning

A Singular Value Thresholding Algorithm for Matrix Completion

Factorization meets the neighborhood: a multifaceted collaborative filtering model

Scope of validity of PSNR in image/video quality assessment

Exact Matrix Completion via Convex Optimization

Greedy approximation

Sparse Approximate Solutions to Semidefinite Programs

CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

Coordinate descent algorithms for lasso penalized regression

Lessons from the Netflix prize challenge

Consistency of trace norm minimization

Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

The elements of statistical learning: data mining, inference and prediction

Maximum-Margin Matrix Factorization

Greed is good: algorithmic results for sparse approximation

MovieLens unplugged: experiences with an occasionally connected recommender system

Eigentaste: A Constant Time Collaborative Filtering Algorithm

Some remarks on greedy algorithms

Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition

An algorithm for quadratic programming

and W

Matrix Computations

Orthogonal Super Greedy Algorithm and Applications in Compressed Sensing ∗

An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems

An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems

Optspace: A Gradient Descent Algorithm on the Grassmann Manifold for Matrix Completion

The Netflix Prize

Regression Shrinkage and Selection via the Lasso

Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php Copyright © by SIAM. Unauthorized reproduction of this article is prohibited

Downloaded 05/05/15 to 129.219.247.33. Redistribution subject to SIAM license or copyright

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names