has a long history and generally centers around a set of known factorizations such as LU, QR, SVD and eigendecompositions. More []. However, with the advent of new methods based on random projections and convex optimization that started in part in the , we are seeing another surge of very diverse algorithms dedicated to many different kinds of matrix factorizations with new constraints based on rank and/or positivity and/or sparsity,… As a result of this large increase in interest, I have decided to keep a list of them here following the success of the .
The sources for this list include the following most excellent sites: , ‘ s , through SDP by , ’s who provide more in-depth additional information. Additional codes were featured also on . The following people provided additional inputs: , .
Most of the algorithms listed below generally rely on using the nuclear norm as a proxy to the rank functional. . Currently, ( and ) consistently allows one to explore other proxies for the rank functional such as the as found by , , . ** is used to show that the algorithm uses another heuristic than the nuclear norm.
In terms of notations, A refers to a matrix, L refers to a low rank matrix, S a sparse one and N to a noisy one. This page lists the different codes that implement the following matrix factorizations: Matrix Completion, Robust PCA , Noisy Robust PCA, Sparse PCA, NMF, Dictionary Learning, MMV, Randomized Algorithms and other factorizations. Some of these toolboxes can sometimes implement several of these decompositions and are listed accordingly. Before I list algorithm here, I generally feature them on Nuit Blanche under the MF tag: or.
Matrix Completion, A = H.*L with H a known mask, L unknown solve for L lowest rank possible
The idea of this approach is to complete the unknown coefficients of a matrix based on the fact that the matrix is low rank:
- : by , , and
- ** by and .The attendant
- : , B. Recht, C. Re, Apr 2011
- : Online Identification and Tracking of Subspaces from Highly Incomplete Information, L. Balzano, R. Nowak, B. Recht, 2010
- : , R. Meka, P. Jain, I.S.Dhillon, 2009
- : SET: an algorithm for consistent matrix completion, W. Dai, O. Milenkovic, 2009
- : An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, K. Toh, S. Yun, 2009
- : Fixed point and Bregman iterative methods for matrix rank minimization, S. Ma, D. Goldfard, L. Chen, 2009
- : A singular value thresholding algorithm for matrix completion, J-F Cai, E.J. Candes, Z. Shen, 2008
Noisy Robust PCA, A = L + S + N with L, S, N unknown, solve for L low rank, S sparse, N noise
- : Randomized Low-rank and Sparse Matrix Decomposition in Noisy Case
- ReProCS: The ()
Robust PCA : A = L + S with L, S, N unknown, solve for L low rank, S sparse
- : Two Codes that go with the paper by and
- ADMM: by . The . The .
- PCP:
- Augmented Lagrange Multiplier (ALM) Method [exact ALM - MATLAB ] [inexact ALM - MATLAB], Reference - , Z. Lin, M. Chen, L. Wu, and Y. Ma (UIUC Technical Report UILU-ENG-09-2215, November 2009)
- Accelerated Proximal Gradient , Reference - , Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen, and Y. Ma (UIUC Technical Report UILU-ENG-09-2214, August 2009)[full SVD version - MATLAB ] [partial SVD version - MATLAB ]
- Dual Method [MATLAB ], Reference - , Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen, and Y. Ma (UIUC Technical Report UILU-ENG-09-2214, August 2009).
- Singular Value Thresholding [MATLAB ]. Reference - , J. -F. Cai, E. J. Candès, and Z. Shen (2008).
- Alternating Direction Method [MATLAB ] , Reference - , X. Yuan, and J. Yang (2009).
- (CPPCA)
Sparse PCA: A = DX with unknown D and X, solve for sparse D
Sparse PCA
- R. Jenatton, G. Obozinski, F. Bach. Structured Sparse Principal Component Analysis. International Conference on Artificial Intelligence and Statistics (AISTATS). [] []
- DSPCA: . Code is.
- PathPCA: A fast greedy algorithm for Sparse PCA. The code is .
Dictionary Learning: A = DX with unknown D and X, solve for sparse X
Some implementation of dictionary learning implement the NMF
- by , , , [The code is released as or ]
- (Matlab implementation of )
- [Matlab implementation of the , a newer implementation by Ron Rubinstein is ]
- [ Matlab ]
- . Matlab implemention is
- .
- by Hadi Zayyani, and .
- [Matlab implementation of ), a faster implementation of NMF can be found , here is a more recent ]
NMF: A = DX with unknown D and X, solve for elements of D,X > 0
- : by , .
- by , , ,
- : C.-J. Lin. . , 19(2007), 2756-2779.
- : contains an optimized C implementation of the Non-Negative Matrix Factorization (NMF) algorithm, described in . We implement the update rules that minimize a weighted SSD error metric. A detailed description of weighted NMF can be found in.
- , Toolboxes for NMF (Non-negative Matrix Factorization) and NTF (Non-negative Tensor Factorization) for BSS (Blind Source Separation)
- [Matlab implementation of ), a faster implementation of NMF can be found , here is a more recent ]
Multiple Measurement Vector (MMV) Y = A X with unknown X and rows of X are sparse.
- by
- by , , [no code]
- by Moshe Mishali and Yonina C. Eldar [ no code]
Blind Source Separation (BSS) Y = A X with unknown A and X and statistical independence between columns of X or subspaces of columns of X
Include Independent Component Analysis (ICA), Independent Subspace Analysis (ISA), and Sparse Component Analysis (SCA). There are many available codes for ICA and some for SCA. Here is a non-exhaustive list of some famous ones (which are not limited to linear instantaneous mixtures). TBC
ICA:
- ICALab:
- BLISS softwares:
- MISEP:
- Parra and Spence’s frequency-domain convolutive ICA:
- C-FICA:
SCA:
- DUET: (the matlab code is given at the end of this pdf document)
- LI-TIFROM:
Randomized Algorithms
These algorithms uses generally random projections to shrink very large problems into smaller ones that can be amenable to traditional matrix factorization methods.
Resource by Michael W. Mahoney
- Randomized Least Squares: ( )
Other factorization
D(T(.)) = L + E with unknown L, E and unknown transformation T and solve for transformation T, Low Rank L and Noise E
Frameworks featuring advanced Matrix factorizations
For the time being, few have integrated the most recent factorizations.
- (Python)
- (Probabilistic PCA, Factor Analysis (FA)…)
- (Python)
- —a package providing PCA methods for incomplete data. R Language
GraphLab / Hadoop
- keeps a .
Books
- .
Example of use
Sources
’s
- ‘ s
- through SDP by
Relevant links
Reference:
本文引用地址：