Sublinear randomized algorithms for skeleton decompositions

Details Sublinear randomized algorithms for skeleton decompositions Sublinear randomized algorithms for skeleton decompositions

2011-10-19

arxiv.org/abs/1110.4193v2

Mathematics

Numerical Analysis

Scientific paper

Let $A$ be a $n$ by $n$ matrix. A skeleton decomposition is any factorization of the form $CUR$ where $C$ comprises columns of $A$, and $R$ comprises rows of $A$. In this paper, we consider uniformly sampling $\l\simeq k \log n$ rows and columns to produce a skeleton decomposition. The algorithm runs in $O(\l^3)$ time, and has the following error guarantee. Let $\norm{\cdot}$ denote the 2-norm. Suppose $A\simeq X B Y^T$ where $X,Y$ each have $k$ orthonormal columns. Assuming that $X,Y$ are incoherent, we show that with high probability, the approximation error $\norm{A-CUR}$ will scale with $(n/\l)\norm{A-X B Y^T}$ or better. A key step in this algorithm involves regularization. This step is crucial for a nonsymmetric $A$ as empirical results suggest. Finally, we use our proof framework to analyze two existing algorithms in an intuitive way.

Affiliated with

Also associated with

No associations

Rating

Sublinear randomized algorithms for skeleton decompositions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sublinear randomized algorithms for skeleton decompositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sublinear randomized algorithms for skeleton decompositions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-596939