Randomized Algorithms for Matrices and Data

DOI10.1561/2200000035zbMath1232.68173OpenAlexW4244670803MaRDI QIDQ3117600

Publication date: 29 February 2012

Published in: Foundations and Trends® in Machine Learning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1561/2200000035

zbMATH Keywords

linear least-squares problem randomized matrix algorithms large-scale data analysis random sampling algorithms statistical leverage low-rank matrix approximation problem random projection algorithms

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Randomized algorithms (68W20)

Related Items

Numerically safe Gaussian elimination with no pivoting ⋮ Wavelet adaptive proper orthogonal decomposition for large-scale flow data ⋮ Stochastic Gradients for Large-Scale Tensor Decomposition ⋮ Energy landscape for large average submatrix detection problems in Gaussian random matrices ⋮ Stable estimation of a covariance matrix guided by nuclear norm penalties ⋮ Efficient alternating least squares algorithms for low multilinear rank approximation of tensors ⋮ Spectral estimation from simulations via sketching ⋮ Gaussian random projections for Euclidean membership problems ⋮ Randomized Local Model Order Reduction ⋮ Nonparametric stochastic approximation with large step-sizes ⋮ Smoothing Splines Approximation Using Hilbert Curve Basis Selection ⋮ Randomized Spectral Clustering in Large-Scale Stochastic Block Models ⋮ LowCon: A Design-based Subsampling Approach in a Misspecified Linear Model ⋮ Error analysis of a model order reduction framework for financial risk analysis ⋮ Randomized Complete Pivoting for Solving Symmetric Indefinite Linear Systems ⋮ A Nonlinear Matrix Decomposition for Mining the Zeros of Sparse Data ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ Randomized quaternion QLP decomposition for low-rank approximation ⋮ An efficient algorithm for computing the approximate t-URV and its applications ⋮ Sketch-based empirical natural gradient methods for deep learning ⋮ Far-field compression for fast kernel summation methods in high dimensions ⋮ Unnamed Item ⋮ Convexification with Bounded Gap for Randomly Projected Quadratic Optimization ⋮ Sharper Bounds for Regularized Data Fitting ⋮ Randomized QLP decomposition ⋮ Randomized matrix-free trace and log-determinant estimators ⋮ Randomized generalized singular value decomposition ⋮ Randomized Quaternion Singular Value Decomposition for Low-Rank Matrix Approximation ⋮ Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation ⋮ Robust manifold broad learning system for large-scale noisy chaotic time series prediction: a perturbation perspective ⋮ Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument ⋮ Model order reduction with oblique projections for large scale wave propagation ⋮ Revisiting the (block) Jacobi subspace rotation method for the symmetric eigenvalue problem ⋮ Randomized algorithms in numerical linear algebra ⋮ Random sampling of bandlimited signals on graphs ⋮ Optimal subsampling for softmax regression ⋮ Practical Sketching Algorithms for Low-Rank Matrix Approximation ⋮ Adaptive iterative Hessian sketch via $A$-optimal subsampling ⋮ Unnamed Item ⋮ Literature survey on low rank approximation of matrices ⋮ Newton-type methods for non-convex optimization under inexact Hessian information ⋮ A randomized singular value decomposition for third-order oriented tensors ⋮ Low Rank Approximation of a Sparse Matrix Based on LU Factorization with Column and Row Tournament Pivoting ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Randomized Subspace Iteration: Analysis of Canonical Angles and Unitarily Invariant Norms ⋮ Parameterized low-rank binary matrix approximation ⋮ Randomized algorithms for the low multilinear rank approximations of tensors ⋮ Core-Sets: Updated Survey ⋮ Wild binary segmentation for multiple change-point detection ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ Introduction to Communication Avoiding Algorithms for Direct Methods of Factorization in Linear Algebra ⋮ Sub-sampled Newton methods ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ An improvement of the parameterized frequent directions algorithm ⋮ On the Numerical Rank of Radial Basis Function Kernels in High Dimensions ⋮ On orthogonal projections for dimension reduction and applications in augmented target loss functions for learning problems ⋮ Unnamed Item ⋮ A geometric probability randomized Kaczmarz method for large scale linear systems ⋮ On b-bit min-wise hashing for large-scale regression and classification with sparse data ⋮ Energy preserving model order reduction of the nonlinear Schrödinger equation ⋮ Randomized model order reduction ⋮ Structure preserving reduced order modeling for gradient systems ⋮ Unbiased predictive risk estimation of the Tikhonov regularization parameter: convergence with increasing rank approximations of the singular value decomposition ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Randomized linear algebra for model reduction. II: Minimal residual methods and dictionary-based approximation ⋮ Multiplicative perturbation bounds for multivariate multiple linear regression in Schatten $p$-norms ⋮ Sparse Principal Component Analysis via Variable Projection ⋮ Editorial: Randomized algorithms for training neural networks ⋮ Geometric component analysis and its applications to data analysis ⋮ A randomized balanced proper orthogonal decomposition technique ⋮ Insights into randomized algorithms for neural networks: practical issues and common pitfalls ⋮ The Fast Cauchy Transform and Faster Robust Linear Regression ⋮ An efficient randomized algorithm for computing the approximate Tucker decomposition ⋮ Tikhonov Regularization and Randomized GSVD ⋮ Approximate nonparametric quantile regression in reproducing kernel Hilbert spaces via random projection ⋮ A consistency theorem for randomized singular value decomposition ⋮ Two fast vector-wise update algorithms for orthogonal nonnegative matrix factorization with sparsity constraint ⋮ Randomized signal processing with continuous frames ⋮ Sparse Learning for Large-Scale and High-Dimensional Data: A Randomized Convex-Concave Optimization Approach ⋮ ASKIT: An Efficient, Parallel Library for High-Dimensional Kernel Summations ⋮ Randomized Sketching Algorithms for Low-Memory Dynamic Optimization ⋮ High-dimensional model recovery from random sketched data by exploring intrinsic sparsity ⋮ Randomized algorithms of maximum likelihood estimation with spatial autoregressive models for large-scale networks ⋮ Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sublinear Cost Low Rank Approximation via Subspace Sampling ⋮ Model-free global likelihood subsampling for massive data ⋮ Two-sample testing of high-dimensional linear regression coefficients via complementary sketching ⋮ Single-pass randomized QLP decomposition for low-rank approximation ⋮ Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching ⋮ Randomized Algorithms for Low-Rank Tensor Decompositions in the Tucker Format ⋮ ISLET: Fast and Optimal Low-Rank Tensor Regression via Importance Sketching ⋮ A probabilistic algorithm for aggregating vastly undersampled large Markov chains ⋮ Estimating and Accounting for Unobserved Covariates in High-Dimensional Correlated Data ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Subspaces Analysis for Random Projection UTV Framework ⋮ RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression ⋮ Practical Leverage-Based Sampling for Low-Rank Tensor Decomposition ⋮ Scalable subspace methods for derivative-free nonlinear least-squares optimization ⋮ One-pass additive-error subset selection for $\ell_p$ subspace approximation and $(k, p)$-clustering ⋮ Randomized algorithms for the computation of multilinear rank-$(\mu_1,\mu_2,\mu_3)$ approximations ⋮ A literature survey of matrix methods for data science ⋮ Pass-efficient randomized LU algorithms for computing low-rank matrix approximation ⋮ Optimal subsampling design for polynomial regression in one covariate ⋮ M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions ⋮ Randomized tensor decomposition for large-scale data assimilation problems for carbon dioxide sequestration ⋮ Subsampling and Jackknifing: A Practically Convenient Solution for Large Data Analysis With Limited Computational Resources ⋮ Model constraints independent optimal subsampling probabilities for softmax regression ⋮ Training very large scale nonlinear SVMs using alternating direction method of multipliers coupled with the hierarchically semi-separable kernel approximations ⋮ Generalized linear models for massive data via doubly-sketching ⋮ Minimum cost flow in the CONGEST model ⋮ Stochastic configuration network based cascade generalized predictive control of main steam temperature in power plants ⋮ On randomized sketching algorithms and the Tracy-Widom law ⋮ The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection ⋮ Randomized Discrete Empirical Interpolation Method for Nonlinear Model Reduction ⋮ Optimal subsampling for functional quantile regression ⋮ Relations Among Some Low-Rank Subspace Recovery Models ⋮ Random Sampling and Efficient Algorithms for Multiscale PDEs ⋮ Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations ⋮ Structured Random Sketching for PDE Inverse Problems ⋮ A Comparative Study of Pairwise Learning Methods Based on Kernel Ridge Regression ⋮ Low-Rank Binary Matrix Approximation in Column-Sum Norm. ⋮ Shallow neural networks for fluid flow reconstruction with limited sensors ⋮ Householder QR Factorization With Randomization for Column Pivoting (HQRRP) ⋮ Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views ⋮ Redundancy Techniques for Straggler Mitigation in Distributed Optimization and Learning ⋮ Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm ⋮ Block Basis Factorization for Scalable Kernel Evaluation ⋮ Randomized Dynamic Mode Decomposition ⋮ Unnamed Item ⋮ Scalable Matrix-Free Adaptive Product-Convolution Approximation for Locally Translation-Invariant Operators ⋮ Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation ⋮ On Approximating Matrix Norms in Data Streams ⋮ Conditioning of Leverage Scores and Computation by QR Decomposition ⋮ Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds ⋮ Subspace Iteration Randomization and Singular Value Problems

Uses Software