Approximate matrix factorisation

The classics

The big six exact matrix deompositions are (Stewart 2000) Cholesky decomposition; pivoted LU decomposition; QR decomposition; spectral decomposition; Schur decomposition; and singular value decomposition.

See Nick Higham’s summary of those.

Approximate decompositions

Mastered QR and LU decompositions? There are now so many ways of factorising matrices that there are not enough acronyms in the alphabet to hold them, especially if you suspect your matrix is sparse, or could be made sparse because of some underlying constraint, or probably could, if squinted at in the right fashion, be such as a graph transition matrix, or Laplacian, or noisy transform of some smooth object, or at least would be close to sparse if you chose the right metric, or…

Your big matrix is close to, in some sense, the (tensor/matrix) product (or sum, or…) of some matrices that are in some way simple (small-rank, small dimension, sparse), possibly with additional constraints. Can you find these simple matrices?

Here’s an example: Godec — A decomposition into low-rank and sparse components which loosely speaking, combines multidimensional factorisation and outlier detection.

There are so many more of these things, depending on your preferred choice of loss function, free variables and such.

Keywords: Matrix sketching, low-rank approximation, traditional dimensionality reduction.

Matrix concentration inequalities turn out to a useful tool that relates here.

I would like to learn more about

• sparse or low-rank matrix approximation as clustering for density estimation, which is how I imagine high-dimensional mixture models would need to work, and thereby also
• Mercer kernel approximation.
• Connection to manifold learning is also probably worth examining.

Igor Carron’s Matrix Factorization Jungle classifies the following problems as matrix-factorisation type.

Kernel Factorizations

…

Spectral clustering

\([A = DX]\) with unknown D and X, solve for sparse X and X_i = 0 or 1

K-Means / K-Median clustering

\([A = DX]\) with unknown D and X, solve for XX^{} = I and X_i = 0 or 1

Subspace clustering

\([A = AX]\) with unknown X, solve for sparse/other conditions on X

Graph Matching

\([A = XBX^{\TOP}]\) with unknown X, B solve for B and X as a permutation

NMF

\([A = DX]\) with unknown D and X, solve for elements of D,X positive

Generalized Matrix Factorization

\([W.*L − W.*UV']\) with W a known mask, U,V unknowns solve for U,V and L lowest rank possible

Matrix Completion

\([A = H.*L]\) with H a known mask, L unknown solve for L lowest rank possible

Stable Principle Component Pursuit (SPCP)/ Noisy Robust PCA

\([A = L + S + N]\) with L, S, N unknown, solve for L low rank, S sparse, N noise

Robust PCA

\([A = L + S]\) with L, S unknown, solve for L low rank, S sparse

Sparse PCA

\([A = DX]\) with unknown D and X, solve for sparse D

Dictionary Learning

\([A = DX]\) with unknown D and X, solve for sparse X

Archetypal Analysis

\([A = DX]\) with unknown D and X, solve for D = AB with D, B positive

Matrix Compressive Sensing (MCS)

find a rank-r matrix L such that \([A(L) ~= b]\) / or \([A(L+S) = b]\)

Multiple Measurement Vector (MMV)

\([Y = A X]\) with unknown X and rows of X are sparse

Compressed sensing

\([Y = A X]\) with unknown X and rows of X are sparse, X is one column.

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

Partial and Online SVD/PCA

…

Tensor Decomposition

Many, many options; see tensor decompositions for some tractable ones.

Truncated Classic PCA is clearly also an example, but is excluded from the list for some reason. Boringness? the fact it’s a special case of Sparse PCA?

I also add

Square root

\(Y = X^{\top}X\) for \(Y\in\mathbbb{R}^{N\times N}, X\in\mathbbb{R}^{N\times n}\), with (typically) \(n<N\).

See also learning on manifolds, compressed sensing, optimisation random linear algebra and clustering, sparse regression…

Why is approximate factorisation ever useful?

For certain types of data matrix, here is a suggestive observation: Udell and Townsend (2019) ask “Why Are Big Data Matrices Approximately Low Rank?”

Matrices of (approximate) low rank are pervasive in data science, appearing in movie preferences, text documents, survey data, medical records, and genomics. While there is a vast literature on how to exploit low rank structure in these datasets, there is less attention paid to explaining why the low rank structure appears in the first place. Here, we explain the effectiveness of low rank models in data science by considering a simple generative model for these matrices: we suppose that each row or column is associated to a (possibly high dimensional) bounded latent variable, and entries of the matrix are generated by applying a piecewise analytic function to these latent variables. These matrices are in general full rank. However, we show that we can approximate every entry of an \(m\times n\) matrix drawn from this model to within a fixed absolute error by a low rank matrix whose rank grows as \(\mathcal{O}(\log(m+n))\). Hence any sufficiently large matrix from such a latent variable model can be approximated, up to a small entrywise error, by a low rank matrix.

Tutorials

• Data mining seminar: Matrix sketching
• Kumar and Schneider have a literature survey on low rank approximation of matrices (Kumar and Shneider 2016)
• Preconditioning tutorial by Erica Klarreich
• Andrew McGregor’s ICML Tutorial Streaming, sampling, sketching
• more at signals and graph.
• Another one that makes the link to clustering is Chris Ding’s Principal Component Analysis and Matrix Factorizations for Learning
• Igor Carron’s Advanced Matrix Factorization Jungle.

Non-negative matrix factorisations

See non-negative matrix factorisations.

As regression

Total Least Squares (a.k.a. orthogonal distance regression, or error-in-variables least-squares linear regression) is a low-rank matrix approximation that minimises the Frobenius divergence from the data matrix. Who knew?

Various other dimensionality reduction techniques can be put in a regression framing, notable Exponential-family PCA.

Sketching

“Sketching” is a common term to describe a certain type of low-rank factorisation, although I am not sure which types. 🏗

(Martinsson 2016) mentions CUR and interpolative decompositions. Does preconditioning fit ?

\([\mathcal{H}]\)-matrix methods

It seems like low-rank matrix factorisation could related to \([\mathcal{H}]\)-matrix methods, as seen in, e.g. covariance matrices, but I do not know enough to say more.

See hmatrix.org for one lab’s backgrounder and their implementation, h2lib, hlibpro for a black-box closed-source one.

Randomized methods

Rather than find an optimal solution, why not just choose a random one which might be good enough? There are indeed randomised versions.

Connections to kernel learning

See (Grosse et al. 2012) for a mind-melting compositional matrix factorization diagram, constructing a search over hierarchical kernel decompositions that also turn out to have some matrix factorisation interpretations.

Bayesian

Nakajima and Sugiyama (2012):

Mnih and Salakhutdinov (2008) proposed a Bayesian maximum a posteriori (MAP) method based on the Gaussian noise model and Gaussian priors on the decomposed matrices. This method actually corresponds to minimizing the squared-loss with the trace-norm penalty (Srebro, Rennie, and Jaakkola 2004) Recently, the variational Bayesian (VB) approach (Attias 1999) has been applied to MF (Lim and Teh 2007; Raiko, Ilin, and Karhunen 2007), which we refer to as VBMF. The VBMF method was shown to perform very well in experiments. However, its good performance was not completely understood beyond its experimental success.

☜ Insert further developments here. Possibly Brouwer’s thesis (Brouwer 2017) or Shakir Mohamed’s (Mohamed 2011) would be a good start, or Benjamin Drave’s tutorial, Probabilistic Matrix Factorization and Xinghao Ding, Lihan He, and Carin (2011).

I am currently sitting in a seminar by He Zhao on Bayesian matrix factorisation, wherein he is building up this tool for discrete data, which is an interesting case. He starts from M. Zhou et al. (2012) and builds up to Zhao et al. (2018), introducing some hierarchical descriptions along the way. His methods seem to be sampling-based rather than variational (?).

Generalized² Linear² models (Gordon 2002) unify nonlinear matrix factorisations with Generalized Linear Models. I had not heard of that until recently; I wonder how common it is?

Implementations

“Enough theory! Plug this algorithm into my data!”

OK.

NMF Toolbox (MATLAB and Python)

Nonnegative matrix factorization (NMF) is a family of methods widely used for information retrieval across domains including text, images, and audio. Within music processing, NMF has been used for tasks such as transcription, source separation, and structure analysis. Prior work has shown that initialization and constrained update rules can drastically improve the chances of NMF converging to a musically meaningful solution. Along these lines we present the NMF toolbox, containing MATLAB and Python implementations of conceptually distinct NMF variants—in particular, this paper gives an overview for two algorithms. The first variant, called nonnegative matrix factor deconvolution (NMFD), extends the original NMF algorithm to the convolutive case, enforcing the temporal order of spectral templates. The second variant, called diagonal NMF, supports the development of sparse diagonal structures in the activation matrix. Our toolbox contains several demo applications and code examples to illustrate its potential and functionality. By providing MATLAB and Python code on a documentation website under a GNU-GPL license, as well as including illustrative examples, our aim is to foster research and education in the field of music processing.

Vowpal Wabbit does this, e.g for recommender systems. It seems the --qr version is more favoured.

HPC for matlab, R, python, c++: libpmf:

LIBPMF implements the CCD++ algorithm, which aims to solve large-scale matrix factorization problems such as the low-rank factorization problems for recommender systems.

NMF (R) 🏗

Matlab: Chih-Jen Lin’s nmf.m - “This tool solves NMF by alternative non-negative least squares using projected gradients. It converges faster than the popular multiplicative update approach. ”

Distributed NMF:

In this repository, we offer both MPI and OPENMP implementation for MU, HALS and ANLS/BPP based NMF algorithms. This can run off the shelf as well easy to integrate in other source code. These are very highly tuned NMF algorithms to work on super computers. We have tested this software in NERSC as well OLCF cluster. The openmp implementation is tested on many different Linux variants with intel processors. The library works well for both sparse and dense matrix. (Fairbanks et al. 2015; Kannan, Ballard, and Park 2016; Kannan 2016)

Spams (C++/MATLAB/python) includes some matrix factorisations in its sparse approx toolbox. (see optimisation)

scikit-learn (python) does a few matrix factorisation in its inimitable batteries-in-the-kitchen-sink way.

nimfa is a Python library for nonnegative matrix factorization. It includes implementations of several factorization methods, initialization approaches, and quality scoring. Both dense and sparse matrix representation are supported.”

Tapkee (C++). Pro-tip — even without coding C++, tapkee does a long list of dimensionality reduction from the CLI.

• PCA and randomized PCA
• Kernel PCA (kPCA)
• Random projection
• Factor analysis

tensorly supports some interesting tensor decompositions.

References