Sublinear randomized algorithms for skeleton decompositions

DOI10.1137/110852310zbMATH Open1277.68296arXiv1110.4193OpenAlexW2964321615MaRDI QIDQ2866239FDOQ2866239

Authors: Jiawei Chiu, Laurent Demanet 

Publication date: 13 December 2013

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

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.

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

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

zbMATH Keywords

interpolative decompositionskeletonlow-rank approximationsNystrom methodcolumn subset selectionCUR

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Cited In (18)

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