Spectral Regularization Algorithms for Learning Large Incomplete Matrices

Rahul MazumderTrevor HastieRobert Tibshirani

article2010JMLR1,484 citations

Develops Soft-Impute, a fast convex algorithm that scales nuclear-norm regularized matrix completion to massive datasets by leveraging low-rank singular value thresholding and warm starts along the entire regularization path.

Listen

Modern data applications, such as commercial recommendation engines, frequently encounter massive datasets where only a small percentage of values are observed. Estimating the missing entries, known as matrix completion, is essential for predicting user preferences and behavior. Traditional mathematical approaches that strictly enforce low-rank constraints are computationally infeasible at scale, while methods that force an exact match to observed data often overfit and perform poorly in real-world settings with noisy measurements.

The article develops and evaluates scalable convex optimization algorithms, primarily an approach named Soft-Impute, to reconstruct large, incomplete, and noisy matrices. The main objective is to provide an efficient framework that minimizes reconstruction error subject to nuclear norm regularization, allowing practitioners to compute a complete path of regularized solutions across varying penalty levels.

The authors analyze the problem using convex relaxation and iterative singular value thresholding. By exploiting the underlying problem structure—specifically decomposing matrices into sparse and low-rank components—the computational cost per iteration scales linearly with matrix dimensions. The methodology is tested on controlled synthetic datasets of varying noise levels and matrix dimensions, including large-scale matrices up to one million by one million entries, as well as the real-world Netflix Prize dataset containing over 100 million ratings.

The evaluations establish four key findings. First, the primary algorithm solves large-scale problems rapidly; it computes a rank-80 approximation for a one-million by one-million matrix in approximately 2.5 hours and fits a rank-40 model on the entire Netflix dataset in 6.6 hours. Second, nuclear norm regularization consistently outperforms exact-fit methods and hard rank constraints in noisy environments, achieving substantially lower prediction error on unobserved entries. Third, when noise levels are high, combining the primary algorithm with an unshrinking post-processing step accurately identifies the true underlying rank. Fourth, hard-thresholding methods perform best only when the noise level is exceptionally low and data is very sparse, but they degrade in noisy regimes.

These findings indicate that organizations can train high-quality recommendation and matrix completion models on full-scale enterprise data without resorting to lossy subsampling or computationally prohibitive exact methods. The ability to compute entire regularization paths with warm starts reduces the risk of overfitting and provides direct operational control over the trade-off between model complexity and prediction accuracy.

Organizations implementing matrix completion should adopt nuclear-norm-based regularization for noisy, real-world data and reserve hard-thresholding techniques for low-noise environments. When deploying these methods, teams should also utilize post-processing unshrinking procedures to optimize rank estimation. However, leaders should note that the theoretical guarantees assume approximately uniform patterns of missing data, an assumption that real-world customer activity data (such as Netflix ratings) often violates. Further refinement and pilot evaluations are recommended to address non-uniform missingness patterns and enhance prediction accuracy before deploying into critical production workflows.

Stanford University University of California, Berkeley reconstruction regularization parameters training sample matrix completion spectral regularization Soft-Impute

arXiv: 0906.2034

Paper: Tensor Completion for Estimating Missing Values in Visual Data, Ji Liu et al. (2009). Introduces convex nuclear-norm relaxation and singular value thresholding schemes for recovering missing entries in multidimensional visual data.
Paper: Full regularization path for sparse principal component analysis, Alexandre d'Aspremont et al. (2007). Pioneers the computation of entire convex regularization paths for low-rank and sparse matrix factorizations.
Paper: Efficient projections onto the l1-ball for learning in high dimensions, John C. Duchi et al. (2008). Provides efficient thresholding and projection algorithms that underpin scalable proximal gradient updates in regularized matrix estimation.
Paper: Collaborative Filtering for Implicit Feedback Datasets, Yifan Hu et al. (2008). Establishes foundational scalable matrix factorization techniques for large, incomplete collaborative filtering datasets.
Paper: Probabilistic Matrix Factorization, Andriy Mnih et al. (2007). Formulates the large-scale collaborative filtering and missing-entry estimation problem on the Netflix benchmark that Soft-Impute targets.
Paper: Convex multi-task feature learning, Andreas Argyriou et al. (2008). Establishes convex spectral regularization formulations for learning low-rank shared structures across multiple tasks.

Paper: Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization, Martin Jaggi (2013). Develops projection-free Frank-Wolfe optimization algorithms for nuclear-norm constrained problems, avoiding repeated full singular value decompositions.
Paper: Robust Subspace Segmentation by Low-Rank Representation, Guangcan Liu et al. (2010). Extends nuclear-norm spectral regularization principles to robust subspace segmentation and corrupted data recovery via Low-Rank Representation.
Paper: Complex Embeddings for Simple Link Prediction, Théo Trouillon et al. (2016). Extends low-rank matrix and tensor completion methods to large-scale relational link prediction using complex embeddings.
Paper: A Three-Way Model for Collective Learning on Multi-Relational Data, Maximilian Nickel et al. (2011). Generalizes low-rank matrix completion and factorization techniques to multi-relational tensor datasets.
Paper: Tensor Decomposition for Signal Processing and Machine Learning, Nicholas D. Sidiropoulos et al. (2016). Provides a comprehensive overview of how low-rank matrix decomposition concepts generalize to higher-order tensors in machine learning.
Paper: SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives, Aaron Defazio et al. (2014). Presents fast incremental proximal gradient methods tailored for non-smooth composite objectives like nuclear norm regularization.
Paper: Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Rie Johnson et al. (2013). Introduces stochastic variance reduction to accelerate first-order optimization routines for composite convex problems.

Cover for Spectral Regularization Algorithms for Learning Large Incomplete Matrices

Abstract

We use convex relaxation techniques to provide a sequence of regularized low-rank solutions for large-scale matrix completion problems. Using the nuclear norm as a regularizer, we provide a simple and very efficient convex algorithm for minimizing the reconstruction error subject to a bound on the nuclear norm. Our algorithm Soft-Impute iteratively replaces the missing elements with those obtained from a soft-thresholded SVD. With warm starts this allows us to efficiently compute an entire regularization path of solutions on a grid of values of the regularization parameter. The computationally intensive part of our algorithm is in computing a low-rank SVD of a dense matrix. Exploiting the problem structure, we show that the task can be performed with a complexity linear in the matrix dimensions. Our semidefinite-programming algorithm is readily scalable to large matrices: for example it can obtain a rank-80 approximation of a 10^6 × 10^6 incomplete matrix with 10^5 observed entries in 2.5 hours, and can fit a rank 40 approximation to the full Netflix training set in 6.6 hours. Our methods show very good performance both in training and test error when compared to other competitive state-of-the art techniques.

Topics

reconstruction regularization parameters training sample

Keywords

matrix completion spectral regularization Soft-Impute matrix rank minimization low-rank matrices proximal forward-backward splitting Lanczos bidiagonalization collaborative filtering nuclear norm regularization regularization path

1. Introduction
2. Context and related work
3. Algorithm and Convergence analysis
3.1 Notation
3.2 Nuclear norm regularization
3.3 Algorithm
3.4 Convergence analysis
4. Computation
5. Generalized spectral regularization: from soft to hard-thresholding
6. Post-processing of 'selectors' and initialization
7. Simulation Studies
7.1 Observations
8. Application to Netflix data
Acknowledgements
Appendix A. Appendix
A.1 Proof of Lemma 1
A.2 Proof of Lemma 3
A.3 Proof of Lemma 4
A.4 Proof of Lemma 5
References

Knowls

Knowl 1 — Nuclear Norm Regularized Least-Squares Matrix Completion
model/method
For a partially observed matrix $X \in \mathbb{R}^{m \times n}$ with observed entry indices $\Omega \subset \{1, \dots, m\} \times \{1, \dots, n\}$ , the projection operator $P_\Omega: \mathbb{R}^{m \times n} \to \mathbb{R}^{m \times n}$ is defined as:

$[P_\Omega(Y)]_{ij} = \begin{cases} Y_{ij} & \text{if } (i,j) \in \Omega \\ 0 & \text{if } (i,j) \notin \Omega \end{cases}$

with complementary projection $P_\Omega^\perp(Y) = Y - P_\Omega(Y)$ .

The convex relaxation for low-rank matrix completion in the presence of noise minimizes the training squared error subject to a nuclear norm penalty:

$\min_{Z \in \mathbb{R}^{m \times n}} f_\lambda(Z) = \frac{1}{2} \|P_\Omega(X) - P_\Omega(Z)\|_F^2 + \lambda \|Z\|_*$

where $\|Z\|_F = \sqrt{\sum_{i,j} Z_{ij}^2}$ is the Frobenius norm, $\|Z\|_* = \sum_{i=1}^{\min(m,n)} \sigma_i(Z)$ is the nuclear norm (sum of singular values of $Z$ ), and $\lambda \ge 0$ is a regularization parameter controlling the shrinkage of the singular values and the rank of the minimizer $\hat{Z}_\lambda$ .
Knowl 2 — Singular Value Soft-Thresholding Operator
theoretical result
For any matrix $W \in \mathbb{R}^{m \times n}$ with rank $r$ and singular value decomposition $W = U D V^T$ , where $D = \text{diag}(d_1, \dots, d_r)$ with $d_1 \ge d_2 \ge \dots \ge d_r > 0$ , the unique global minimizer of the problem

$\min_{Z \in \mathbb{R}^{m \times n}} \frac{1}{2} \|W - Z\|_F^2 + \lambda \|Z\|_*$

is given by the matrix soft-thresholding operator $\mathcal{S}_\lambda(W)$ :

$\mathcal{S}_\lambda(W) = U D_\lambda V^T$

where $D_\lambda = \text{diag}((d_1 - \lambda)_+, \dots, (d_r - \lambda)_+)$ and $(t)_+ = \max(t, 0)$ . Furthermore, the operator $\mathcal{S}_\lambda(\cdot)$ is non-expansive in the Frobenius norm:

$\|\mathcal{S}_\lambda(W_1) - \mathcal{S}_\lambda(W_2)\|_F^2 \le \|W_1 - W_2\|_F^2$
Knowl 3 — Soft-Impute Algorithm for Matrix Completion
algorithm
The Soft-Impute algorithm computes regularized low-rank matrix completions across a decreasing sequence of regularization parameters $\Lambda = \{\lambda_1 > \lambda_2 > \dots > \lambda_K\}$ using warm restarts.
Input: Observed matrix entries $P_\Omega(X)$ , tolerance $\epsilon > 0$ , grid $\Lambda = \{\lambda_1 > \dots > \lambda_K\}$
Output: Sequence of matrix estimates $\hat{Z}_{\lambda_1}, \dots, \hat{Z}_{\lambda_K}$
Initialize $Z^{\text{old}} \leftarrow 0$
for each $\lambda \in \{\lambda_1, \dots, \lambda_K\}$ do
    repeat
         $W \leftarrow P_\Omega(X) + P_\Omega^\perp(Z^{\text{old}})$
         $Z^{\text{new}} \leftarrow \mathcal{S}_\lambda(W)$
         $ratio \leftarrow \|Z^{\text{new}} - Z^{\text{old}}\|_F^2 / \|Z^{\text{old}}\|_F^2$
         $Z^{\text{old}} \leftarrow Z^{\text{new}}$
    until $ratio < \epsilon$
     $\hat{Z}_\lambda \leftarrow Z^{\text{new}}$
return $\hat{Z}_{\lambda_1}, \dots, \hat{Z}_{\lambda_K}$
Here, $\mathcal{S}_\lambda(W)$ performs singular value thresholding by soft-thresholding the singular values of $W$ at level $\lambda$ . The algorithm requires no step-size parameter and uses the solution at $\lambda_k$ as the initial point for $\lambda_{k+1}$ .
Knowl 4 — Convergence of the Soft-Impute Sequence
theoretical result
Let $f_\lambda(Z) = \frac{1}{2}\|P_\Omega(X) - P_\Omega(Z)\|_F^2 + \lambda \|Z\|_*$ , and define the surrogate function

$Q_\lambda(Z | \tilde{Z}) = \frac{1}{2}\|P_\Omega(X) + P_\Omega^\perp(\tilde{Z}) - Z\|_F^2 + \lambda \|Z\|_*$

For a fixed $\lambda \ge 0$ and any starting point $Z_\lambda^0$ , let the sequence $Z_\lambda^{k+1} = \arg\min_Z Q_\lambda(Z | Z_\lambda^k) = \mathcal{S}_\lambda(P_\Omega(X) + P_\Omega^\perp(Z_\lambda^k))$ . The sequence satisfies:
1. Monotonic objective descent: $f_\lambda(Z_\lambda^{k+1}) \le Q_\lambda(Z_\lambda^{k+1} | Z_\lambda^k) \le f_\lambda(Z_\lambda^k)$ .
2. Monotonic step differences: $\|Z_\lambda^{k+1} - Z_\lambda^k\|_F \le \|Z_\lambda^k - Z_\lambda^{k-1}\|_F$ , and $\|Z_\lambda^{k+1} - Z_\lambda^k\|_F \to 0$ as $k \to \infty$ .
3. Monotonic distance reduction to solutions: for any global minimizer $\hat{Z}_\lambda$ , $\|\hat{Z}_\lambda - Z_\lambda^k\|_F \le \|\hat{Z}_\lambda - Z_\lambda^{k-1}\|_F$ .
4. Global convergence: $Z_\lambda^k$ converges to a limit $Z_\lambda^\infty$ that is a global minimizer of $f_\lambda(Z)$ and satisfies the fixed-point equation $Z = \mathcal{S}_\lambda(P_\Omega(X) + P_\Omega^\perp(Z))$ .
Knowl 5 — Sparse-plus-Low-Rank SVD Computation
model/method
In the Soft-Impute update step, the dense $m \times n$ matrix argument $W = P_\Omega(X) + P_\Omega^\perp(Z^k)$ is decomposed into a sparse matrix plus a low-rank matrix:

$W = \underbrace{(P_\Omega(X) - P_\Omega(Z^k))}_{Y_{\text{SP}} \text{ (sparse)}} + \underbrace{Z^k}_{Y_{\text{LR}} \text{ (low rank)}}$

where $Y_{\text{SP}}$ has non-zero entries only on $\Omega$ (at most $|\Omega|$ non-zeros), and $Y_{\text{LR}}$ has low rank $r \ll \min(m, n)$ with factored representation $Z^k = U_k D_k V_k^T$ .

Evaluating matrix-vector multiplications $W b_1$ (for $b_1 \in \mathbb{R}^n$ ) and $W^T b_2$ (for $b_2 \in \mathbb{R}^m$ ) does not require forming $W$ explicitly:
- Multiplying $Y_{\text{SP}} b_1$ requires $O(|\Omega|)$ operations.
- Multiplying $Y_{\text{LR}} b_1 = U_k (D_k (V_k^T b_1))$ requires $O((m + n)r)$ operations.
Using iterative Lanczos bidiagonalization with partial reorthogonalization (such as PROPACK), computing the leading $r$ singular vectors has computational complexity $O(|\Omega|r + (m+n)r^2)$ , which is linear in matrix dimensions $m, n$ and observation size $|\Omega|$ .
Knowl 6 — Post-Processing Unshrinking of Singular Values (Pp-SI)
model/method
Because nuclear norm regularization applies uniform shrinkage $\lambda$ to all singular values, the number of retained singular vectors can exceed the true rank of the underlying matrix. The post-processing procedure (Pp-SI) unshrinks the singular values by solving an ordinary non-negative least-squares problem over the support of the observed entries.

Given the SVD $Z_\lambda = U D_\lambda V^T = \sum_{i=1}^{r_\lambda} d_i u_i v_i^T$ obtained from Soft-Impute with rank $r_\lambda$ , the un-shrunk weights $\hat{\alpha} = (\hat{\alpha}_1, \dots, \hat{\alpha}_{r_\lambda})^T$ are computed via:

$\hat{\alpha} = \arg\min_{\alpha_i \ge 0, \, i=1,\dots,r_\lambda} \left\| P_\Omega(X) - \sum_{i=1}^{r_\lambda} \alpha_i P_\Omega(u_i v_i^T) \right\|_F^2$

The post-processed low-rank matrix estimator is:

$Z_\lambda^u = U \text{diag}(\hat{\alpha}_1, \dots, \hat{\alpha}_{r_\lambda}) V^T$

Because $r_\lambda$ is typically small, this involves fitting only $r_\lambda$ parameters and avoids overfitting while correcting the shrinkage bias.
Knowl 7 — Hard-Impute Algorithm and Concave Spectral Regularization
algorithm
To bridge the gap between nuclear norm ( $\ell_1$ -type) and rank ( $\ell_0$ -type) penalties, matrix completion can be regularized via concave penalties on singular values $\sum_j p(\gamma_j(Z); \mu)$ :

$\min_Z f_{p,\lambda}(Z) = \frac{1}{2} \|P_\Omega(X) - P_\Omega(Z)\|_F^2 + \lambda \sum_j p(\gamma_j(Z); \mu)$

For the $\ell_0$ rank penalty $p(t) = I(t > 0)$ , the corresponding thresholding operator is the hard-thresholding operator $\mathcal{S}_\lambda^H(W) = U D_q V^T$ , where $D_q = \text{diag}(d_1, \dots, d_q, 0, \dots, 0)$ retains the singular values of $W$ that exceed $\lambda$ .
Input: Observed entries $P_\Omega(X)$ , tolerance $\epsilon > 0$ , grid $\Lambda = \{\lambda_1 > \dots > \lambda_K\}$ , warm starts $\tilde{Z}_{\lambda_k}$
Output: Sequence of solutions $\hat{Z}_{H,\lambda_1}, \dots, \hat{Z}_{H,\lambda_K}$
for each $\lambda \in \{\lambda_1, \dots, \lambda_K\}$ do
     $Z^{\text{old}} \leftarrow \tilde{Z}_\lambda$
    repeat
         $W \leftarrow P_\Omega(X) + P_\Omega^\perp(Z^{\text{old}})$
         $Z^{\text{new}} \leftarrow \mathcal{S}_\lambda^H(W)$
         $ratio \leftarrow \|Z^{\text{new}} - Z^{\text{old}}\|_F^2 / \|Z^{\text{old}}\|_F^2$
         $Z^{\text{old}} \leftarrow Z^{\text{new}}$
    until $ratio < \epsilon$
     $\hat{Z}_{H,\lambda} \leftarrow Z^{\text{new}}$
return $\hat{Z}_{H,\lambda_1}, \dots, \hat{Z}_{H,\lambda_K}$
Warm starts $\tilde{Z}_\lambda$ are typically initialized using the Soft-Impute solution or its un-shrunk version (Pp-SI).
Knowl 8 — Matrix Completion Performance Under Varying Noise Regimes
empirical result
In synthetic matrix completion experiments ( $100 \times 100$ matrices, varying missingness and signal-to-noise ratio $\text{SNR} = \sqrt{\text{var}(U V^T)/\text{var}(\text{noise})}$ ), performance varies substantially across methods depending on noise level:
1. High noise regime ( $\text{SNR} = 1$ , $50\%$ missing entries, true rank $r \in \{6, 10\}$ ): Soft-Impute and Pp-SI achieve the lowest test error. Pp-SI correctly identifies the underlying matrix rank at its test error minimum. Hard-Impute and OptSpace perform poorly because hard rank constraints aggressively fit noise. Singular Value Thresholding (SVT) with exact fitting constraints overfits severely, resulting in ranks $> 60$ and high prediction error.
2. Low noise regime ( $\text{SNR} = 10$ , $80\%$ missing entries, true rank $r = 5$ ): Hard-Impute and OptSpace achieve the lowest prediction error and sharpest rank recovery, outperforming Soft-Impute because shrinkage bias becomes the dominant source of error when noise is small.

Knowl 9 — Scalability Benchmarks of Soft-Impute on Large Incomplete Matrices

data/table

The execution runtime and effective rank of Soft-Impute were benchmarked on a single 3 GHz processor across synthetic matrices of dimensions up to $10^6 \times 10^6$ with varying observation counts $|\Omega|$ and SNR values, using convergence tolerance $10^{-4}$ on the relative objective improvement.

$(m, n)$	$\|\Omega\|$	true rank	SNR	effective rank	time(s)
$(3 \times 10^4, 10^4)$	$10^4$	15	1	(13, 47, 80)	(41.9, 124.7, 305.8)
$(10^5, 10^5)$	$10^4$	15	10	(5, 14, 32, 62)	(37, 74.5, 199.8, 653)
$(10^5, 10^5)$	$10^5$	15	10	(18, 80)	(202, 1840)
$(5 \times 10^5, 5 \times 10^5)$	$10^4$	15	10	11	628.14
$(5 \times 10^5, 5 \times 10^5)$	$10^5$	15	1	(3, 11, 52)	(341.9, 823.4, 4810.75)
$(10^6, 10^6)$	$10^5$	15	1	80	8906

The benchmark demonstrates linear scalability with matrix dimension: a rank-80 model on a $10^6 \times 10^6$ matrix with $10^5$ entries converges in under 2.5 hours (8,906 s), and a rank-11 model on a $5 \times 10^5 \times 5 \times 10^5$ matrix with $10^4$ observed entries finishes in under 11 minutes (628.14 s).

Knowl 10 — Performance of Hard-Impute on the Full Netflix Dataset

data/table

Hard-Impute was applied to the complete Netflix movie ratings dataset ( $480,189$ customers, $17,770$ movies, and $100,480,507$ observed ratings, corresponding to approximately $1\%$ observed entries) after subtracting movie and customer mean ratings. Models were evaluated across target ranks on the $1.4$ million rating probe set.

Here, train error is the fraction of squared error relative to a zero estimator, and RMSE is root mean squared error on the probe set. The rank-40 model achieves an RMSE of 0.965 in 6.6 hours on a single 3 GHz processor, verifying the computational feasibility of spectral imputation algorithms on datasets with over $10^8$ observed entries without data subsampling.

Coverage note — None was omitted; all core theoretical results, algorithms (Soft-Impute, Hard-Impute, Post-Processing), computational mechanics, and empirical experiments have been captured.

References

1.Samuel Burer and Renato D.C. Monteiro. Local minima and convergence in low-rank semidefinite programming. Mathematical Programming, 103(3):427–631, 2005.
2.Stephen Boyd. Ee 364b: Lecture notes, stanford university, 2008.
3.Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
4.Jian-Feng Cai, Emmanuel J. Candes, and Zuowei Shen. A singular value thresholding algorithm for matrix completion, 2008.
5.Emmanuel Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 2008.
6.Emmanuel J. Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion, 2009.
7.P. L. Combettes and V. R. Wajs. Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul., 4(4):1168–1200, 2005.
8.D. Donoho, I. Johnstone, G. Kerkyachairan, and D. Picard. Wavelet shrinkage; asymptopia? (with discussion). J. Royal. Statist. Soc., 57:201–337, 1995.
9.M. Fazel. Matrix Rank Minimization with Applications. PhD thesis, Stanford University, 2002.
10.Jerome Friedman, Trevor Hastie, Holger Hoefling, and Robert Tibshirani. Pathwise coordinate optimization. Annals of Applied Statistics, 2(1):302–332, 2007.
11.Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American Statistical Association, 96(456):1348–1360(13), 2001.
12.Jerome Friedman. Fast sparse regression and classification. Technical report, Department of Statistics, Stanford University, 2008.
13.Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning, Second Edition: Data Mining, Inference, and Prediction (Springer Series in Statistics). Springer New York, 2 edition, 2009.
14.Trevor Hastie, Robert Tibshirani, Gavin Sherlock, Michael Eisen, Patrick Brown, and David Botstein. Imputing missing data for gene expression arrays. Technical report, Division of Biostatistics, Stanford University, 1999.
15.Raghunandan H. Keshavan, Sewoong Oh, and Andrea Montanari. Matrix completion from a few entries. CoRR, abs/0901.3150, 2009.
16.R.M. Larsen. Propack-software for large and sparse svd calculations.
17.R. M. Larsen. Lanczos bidiagonalization with partial reorthogonalization. Technical Report DAIMI PB-357, Department of Computer Science, Aarhus University, 1998.
18.Z. Liu and L. Vandenberghe. Interior-point method for nuclear norm approximation with application to system identfication. submitted to Mathematical Programming, 2008.
19.S. Ma, D. Goldfarb, and L. Chen. Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization. ArXiv e-prints, May 2009.
20.Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, 2007.
21.Salakhutdinov R. R., A. Mnih, and G. E Hinton. Restricted boltzmann machines for collaborative filtering. In International Conference on Machine Learning, Corvallis, Oregon., 2007.
22.Jason Rennie and Nathan Srebro. Fast maximum margin matrix factorization for collaborative prediction. 22nd International Conference on Machine Learning, 2005.
23.Nathan Srebro, Noga Alon, and Tommi Jaakkola. Generalization error bounds for collaborative prediction with low-rank matrices. Advances in Neural Information Processing Systems, 2005.
24.Nathan Srebro and Tommi Jaakkola. Weighted low-rank approximations. In In 20th International Conference on Machine Learning, pages 720–727. AAAI Press, 2003.
25.ACM SIGKDD and Netflix. Soft modelling by latent variables: the nonlinear iterative partial least squares (NIPALS) approach. In Proceedings of KDD Cup and Workshop, 2007.
26.Nathan Srebro, Jason Rennie, and Tommi Jaakkola. Maximum margin matrix factorization. Advances in Neural Information Processing Systems, 17, 2005.
27.Olga Troyanskaya, Michael Cantor, Gavin Sherlock, Pat Brown, Trevor Hastie, Robert Tibshirani, David Botstein, and Russ B. Altman. Missing value estimation methods for dna microarrays. Bioinformatics, 17(6):520–525, 2001.
28.R. Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, Series B, 58:267–288, 1996.
29.Gabor Takacs, Istvan Pilaszy, Bottyan Nemeth, and Domonkos Tikk. Scalable collaborative filtering approaches for large recommender systems. Journal of Machine Learning Research, 10:623–656, 2009.
30.Cun Hui Zhang. Penalized linear unbiased selection. Technical report, Departments of Statistics and Biostatistics, Rutgers University, 2007.
31.P. Zhao and B. Yu. On model selection consistency of lasso. Journal of Machine Learning Research, 7:2541–2563, 2006.

Citation

MLA

Mazumder, R., et al. “Spectral Regularization Algorithms for Learning Large Incomplete Matrices”. Journal of Machine Learning Research, vol. 11, no. 80, 2010, pp. 2287–322, https://www.jmlr.org/papers/v11/mazumder10a.html.

APA

Mazumder, R., Hastie, T., & Tibshirani, R. (2010). Spectral Regularization Algorithms for Learning Large Incomplete Matrices. Journal of Machine Learning Research, 11(80), 2287–2322. https://www.jmlr.org/papers/v11/mazumder10a.html

Chicago

Mazumder, R., T. Hastie, and R. Tibshirani. 2010. “Spectral Regularization Algorithms for Learning Large Incomplete Matrices”. Journal of Machine Learning Research 11 (80): 2287–2322. https://www.jmlr.org/papers/v11/mazumder10a.html.

Harvard

Mazumder, R., Hastie, T. and Tibshirani, R. (2010) “Spectral Regularization Algorithms for Learning Large Incomplete Matrices”, Journal of Machine Learning Research, 11(80), pp. 2287–2322. Available at: https://www.jmlr.org/papers/v11/mazumder10a.html.

Vancouver

1. Mazumder R, Hastie T, Tibshirani R (2010) Spectral Regularization Algorithms for Learning Large Incomplete Matrices. Journal of Machine Learning Research 11:2287–2322

BibTeX

@article{JMLR:v11:mazumder10a,
  author  = {Rahul Mazumder and Trevor Hastie and Robert Tibshirani},
  title   = {Spectral Regularization Algorithms for Learning Large Incomplete Matrices},
  journal = {Journal of Machine Learning Research},
  year    = {2010},
  volume  = {11},
  number  = {80},
  pages   = {2287--2322},
  url     = {http://jmlr.org/papers/v11/mazumder10a.html}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

rank	time (hrs)	train error	RMSE
20	3.3	0.217	0.986
30	5.8	0.203	0.977
40	6.6	0.194	0.965
60	9.7	0.181	0.966

Spectral Regularization Algorithms for Learning Large Incomplete Matrices

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Nuclear Norm Regularized Least-Squares Matrix Completion

Knowl 2 — Singular Value Soft-Thresholding Operator

Knowl 3 — Soft-Impute Algorithm for Matrix Completion

Knowl 4 — Convergence of the Soft-Impute Sequence

Knowl 5 — Sparse-plus-Low-Rank SVD Computation

Knowl 6 — Post-Processing Unshrinking of Singular Values (Pp-SI)

Knowl 7 — Hard-Impute Algorithm and Concave Spectral Regularization