Sublinear randomized algorithms for skeleton decompositions

DOI10.1137/110852310MaRDI QIDQ2866239zbMATHOpenAlexFDO

Authors Jiawei Chiu, Laurent Demanet

Publication date 13 December 2013

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.4193

zbMATH Keywords

interpolative decompositionskeletonlow-rank approximationsNystrom methodcolumn subset selectionCUR

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Abstract: 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 $lsimeqklogn$ rows and columns to produce a skeleton decomposition. The algorithm runs in $O(l^3)$ time, and has the following error guarantee. Let $ormcdot$ denote the 2-norm. Suppose $AsimeqXB{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 $ormA-CUR$ will scale with $(n/l)ormA-XB{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.

Recommendations

• A faster algorithm for computing straight skeletons
• A faster algorithm for computing straight skeletons
• Fast algorithms for computing \(\beta\)-skeletons and their relatives.
• Linear-time computation of optimal subgraphs of decomposable graphs
• Sublinear Geometric Algorithms
• Sublinear geometric algorithms
• Tight bounds for the subspace sketch problem with applications
• Tight Bounds for the Subspace Sketch Problem with Applications
• Sublinear graph approximation algorithms

Cited in

(18)

• Interpolative Decomposition Butterfly Factorization
• Perturbations of CUR Decompositions
• MISTER-T: an open-source software package for quantum optimal control of multi-electron systems on arbitrary geometries
• A low-rank approach to the computation of path integrals
• Generalized pseudoskeleton decompositions
• Matrices with hierarchical low-rank structures
• Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
• Matrix concentration inequalities via the method of exchangeable pairs
• Linear-time CUR approximation of BEM matrices
• Sublinear-time quadratic minimization via spectral decomposition of matrices
• Literature survey on low rank approximation of matrices
• Robust CUR Decomposition: Theory and Imaging Applications
• Fast algorithms for the multi-dimensional Jacobi polynomial transform
• Mode-wise tensor decompositions: multi-dimensional generalizations of CUR decompositions
• A note on tensor chain approximation
• Optimal approximation of a large matrix by a sum of projected linear mappings on prescribed subspaces
• Perspectives on CUR decompositions
• Fast multidimensional convolution in low-rank tensor formats via cross approximation

This page was built for publication: Sublinear randomized algorithms for skeleton decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2866239)