# Presentation: 211967

## Extracting Structure from Matrices & Tensors by Random Sampling

- Michael W. Mahoney
- Yale University
*michael.mahoney@yale.edu*
- (joint work with **Petros Drineas** and **Ravi Kannan**)
- @ ARCC Workshop on Tensor Decompositions

## Motivation

_**Goal:**_ To develop and analyze fast Monte-Carlo algorithms for performing useful computations on large matrices (and tensors):
-  Matrix Multiplication
-  Computation of the SVD
-  Computation of the CUR decomposition
-  Testing feasibility of linear programs

- Such matrix computations generally require time which is *superlinear* in the number of nonzero elements of the matrix, e.g., n3 in practice.

- These and related algorithms are useful in applications where the datasets are modeled by matrices (or tensors) and are extremely large.

## Motivation (cont’d)

- In many applications large matrices appear (too large to store in RAM).
-  We can make a few “passes” (sequential READS) through the matrices.
-  We can create and store a small “sketch” of the matrices in RAM.
-  Computing the “sketch” should be a very fast process.
- Discard the original matrix and work with the “sketch”.

## Our approach & our results

- A “sketch” consisting of a **few rows/columns** of the matrix is adequate for efficient approximations.
- We draw the rows/columns randomly, using **non-uniform sampling**; rows/columns are picked with probability proportional to their lengths.

## Approximating A by CUR

- 	Given a **large** m-by-n matrix A (stored on disk), compute an approximation A’=CUR to A such that:
- A’=CUR is stored in O(m+n) space, after making **two **passes through A, and using O(m+n) additional space and time.

- A’=CUR satisfies, with high probability,

## Computing C and R

- C consists of c = O(k/ε2) columns of A.
- R consists of r = O(k/ε2) rows of A.
- C and R are created using **non-uniform sampling:             .  **

## Computing U

- 	The CUR algorithm essentially expresses every row of the matrix A as a linear combination of a small subset of the rows of A.
- This small subset consists of the rows in R.
- Given a row of A – say A(i) – the algorithm computes the “best fit” for the row A(i) using the rows in R as the basis.

- Notice that only c = O(1) elements of the i-th row are given as input. However, a vector of coefficients *u* can still be computed. The whole process runs in O(m) time.

## Main Theorem

- Assume Ak is the “best” rank k approximation to A (through SVD). Then
- To achieve (1), we set r = O(k/ε2) rows and c = O(k/ε2) columns.
- To achieve (2), r = O(1/ε2) rows and c = O(1/ε2) columns suffice.

## A starting point for CUR

- C:\Petros\Image Processing\baboondet.eps

- Creator:

- MATLAB, The Mathworks, Inc.

- Preview:

- This EPS picture was not saved

- with a preview included in it.

- Comment:

- This EPS picture will print to a

- PostScript printer, but not to

- other types of printers.

- Original matrix

- After sampling columns

- Compute the top k left singular vectors of the matrix C and store them in the 512-by-k matrix Hk.
- A and HkHkTA  are close.

- A

## A starting point for CUR (cont’d)	

- Title:

- C:\Petros\Image Processing\baboondet.eps

- Creator:

- MATLAB, The Mathworks, Inc.

- Preview:

- This EPS picture was not saved

- with a preview included in it.

- Comment:

- This EPS picture will print to a

- PostScript printer, but not to

- other types of printers.

- A

- Question: How is HkHkTA related to CUR?
- Answer:  If we replace A by a matrix which consists of a carefully scaled copy of the rows “revealed” in R, then we get CUR!

- HkHkTA

## A straightforward extension to tensors

*(Preliminary results - work in progress)*

## A recursive extension of CUR to tensors

*(Preliminary results - work in progress)*

## For more details:http://www.cs.rpi.edu/~drinephttp://www.cs.yale.edu/homes/mmahoney

- Thank you!