Sublinear randomized algorithms for skeleton decompositions

DOI10.1137/110852310MaRDI QIDQ2866239zbMATH OpenOpenAlexFDO

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

column subset selectionCURinterpolative decompositionlow-rank approximationsNystrom methodskeleton

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 -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

(24)

• Linear-time CUR approximation of BEM matrices
• Perspectives on CUR decompositions
• A low-rank approach to the computation of path integrals
• Matrix concentration inequalities via the method of exchangeable pairs
• Fast algorithms for the multi-dimensional Jacobi polynomial transform
• Generalized pseudoskeleton decompositions
• Matrices with hierarchical low-rank structures
• Literature survey on low rank approximation of matrices
• Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
• Sublinear-time quadratic minimization via spectral decomposition of matrices
• Interpolative Decomposition Butterfly Factorization
• Mode-wise tensor decompositions: multi-dimensional generalizations of CUR decompositions
• A note on tensor chain approximation
• Fast multidimensional convolution in low-rank tensor formats via cross approximation
• Perturbations of CUR Decompositions
• Robust CUR Decomposition: Theory and Imaging Applications
• MISTER-T: an open-source software package for quantum optimal control of multi-electron systems on arbitrary geometries
• Optimal approximation of a large matrix by a sum of projected linear mappings on prescribed subspaces
• Adaptive randomized pivoting for column subset selection, DEIM, and low-rank approximation
• Efficient quaternion CUR method for low-rank approximation to quaternion matrix
• Low-rank approximation of parameter-dependent matrices via CUR decomposition
• Accuracy and stability of CUR decompositions with oversampling
• A sublinear-time randomized algorithm for column and row subset selection based on strong rank-revealing QR factorizations
• Leverage score-based quaternion CUR decomposition: gap error analysis and applications

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)