matrix decomposition

1. CLUSTERED MATRIX APPROXIMATION

SIAM [Society for Industrial and Applied Mathematics] 2016

1. develop a clustered matrix approximation framework
   1. Divide the matrix into different groups
2. particularly well suited for problems with large-scale sparse matrices

Abstract

benefits

1. preserve the important structure presented in the original matrix;
2. contain both global-scale and local-scale information
3. efficient both in computational speed and memory usage
4. resulting approximations more accurate with less memory usage than truncated SVD approximations, which are optimal with respect to rank.
5. flexible: modified in various ways [what ways?]

method

1. derive a probabilistic approach that uses randomness to compute a clustered matrix approximation within the developed framework?.
2. We further prove deterministic and probabilistic bounds of the resulting approximation error.

Introduction

• approximate with low-rank , has been studied extensively in the literature
• bottleneck: with large amounts of data is often memory consumption and not the rank of the approximation
  • In this setting, our method produces a considerably more accurate matrix approximation with memory usage that is the same as or less than that of the truncated SVD approximation, which is optimal with respect to rank.

steps

1. a clustering or coclustering step so that the rows and columns of a given matrix are partitioned into a number of groups;
2. reordering the rows and columns according to cluster a�affiliation and extracting sufficiently dense blocks;
3. computing low-rank approximations of these dense blocks;
4. combining the blockwise approximations into an approximation of the entire
   matrix.

explanation

Computing truncated SVD approximations is relatively expensive, one may wish to trade off� computation time against some slight loss inaccuracy. Probabilistic algorithms for matrix approximation [21] give the means for this kind of trade-off�.

• develop and detail the method

Preliminaries

rely on a number of concepts:

• efficient graph clustering;
• bipartite graph coclustering;
• low-rank matrix approximations;
• stochastic methods for low rank matrix approximations.

Bipartite graph: is a graph whose vertices can be divided into two disjoint and independent sets and such that every edge connects a vertex in to one in . and are usually called the parts of the graph

1. assume that we can partition the graph and obtain disjoint sets

   , with . Without loss of generality, we can assume that vertices in are sorted in strictly increasing order. Then matrix has form
   

1. given and rank
2. standard Gausion matrix , is a small oversampling parameter (typically set to 5 ~ 10)
3. 
4. : orthonormal basis
5. the corresponding low rank approximation is given by
6. 
7. 

Clustered low rank matrix approximations

However , it used existing clusters method... as it is more about computing

End.

2. Improved Nystrom Low-Rank Approximation and Error Analysis

This paper presents detailed studies on the Nystrom sampling scheme and in particular, an error analysis that directly relates the Nystrom approximation quality with the encoding powers of the landmark points.

Introduction

Kernel methods play a central role in machine learning and have demonstrated huge success in modeling real-world data with highly complex, nonlinear structures.