Tensor-structured sketching for constrained least squares
From MaRDI portal
Random matrices (algebraic aspects) (15B52) Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry) (52A21) Random matrices (probabilistic aspects) (60B20) Statistical aspects of big data and data science (62R07) Direct numerical methods for linear systems and matrix inversion (65F05)
Abstract: Constrained least squares problems arise in many applications. Their memory and computation costs are expensive in practice involving high-dimensional input data. We employ the so-called "sketching" strategy to project the least squares problem onto a space of a much lower "sketching dimension" via a random sketching matrix. The key idea of sketching is to reduce the dimension of the problem as much as possible while maintaining the approximation accuracy. Tensor structure is often present in the data matrices of least squares, including linearized inverse problems and tensor decompositions. In this work, we utilize a general class of row-wise tensorized sub-Gaussian matrices as sketching matrices in constrained optimizations for the sketching design's compatibility with tensor structures. We provide theoretical guarantees on the sketching dimension in terms of error criterion and probability failure rate. In the context of unconstrained linear regressions, we obtain an optimal estimate for the sketching dimension. For optimization problems with general constraint sets, we show that the sketching dimension depends on a statistical complexity that characterizes the geometry of the underlying problems. Our theories are demonstrated in a few concrete examples, including unconstrained linear regression and sparse recovery problems.
Recommendations
- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
- A statistical perspective on randomized sketching for ordinary least-squares
- Practical leverage-based sampling for low-rank tensor decomposition
- Structured random sketching for PDE inverse problems
- ISLET: fast and optimal low-rank tensor regression via importance sketching
Cites work
- A fast randomized algorithm for overdetermined linear least-squares regression
- A Multilinear Singular Value Decomposition
- A Practical Randomized CP Tensor Decomposition
- A sparse Johnson-Lindenstrauss transform
- Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
- Compressed matrix multiplication
- Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
- Concentration inequalities for polynomials in \(\alpha\)-sub-exponential random variables
- Convex optimization: algorithms and complexity
- Estimates of moments and tails of Gaussian chaoses
- Extensions of Lipschitz mappings into a Hilbert space
- Finding frequent items in data streams
- Guarantees for the Kronecker fast Johnson-Lindenstrauss transform using a coherence and sampling argument
- High-dimensional probability. An introduction with applications in data science
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Improved analysis of the subsampled randomized Hadamard transform
- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Majorizing measures: The generic chaining
- Multilinear tensor regression for longitudinal relational data
- On sparse reconstruction from Fourier and Gaussian measurements
- Optimization methods for large-scale machine learning
- Randomized Sketches of Convex Programs With Sharp Guarantees
- Reconstruction and subgaussian operators in asymptotic geometric analysis
- Sampling algorithms for l₂ regression and applications
- Sketching as a tool for numerical linear algebra
- Some inequalities for Gaussian processes and applications
- Sparse Sampling for Inverse Problems With Tensors
- Squared-norm empirical processes
- Structured random sketching for PDE inverse problems
- Tensor Decompositions and Applications
- Tensor decompositions for learning latent variable models
- The Generic Chaining
Cited in
(11)- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
- Randomized sketching algorithms for low-memory dynamic optimization
- ISLET: fast and optimal low-rank tensor regression via importance sketching
- Practical leverage-based sampling for low-rank tensor decomposition
- Structured random sketching for PDE inverse problems
- Johnson–Lindenstrauss Embeddings with Kronecker Structure
- Sketch‐and‐project methods for tensor linear systems
- Robust Recovery of Low-Rank Matrices and Low-Tubal-Rank Tensors from Noisy Sketches
- Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-Order Convergence
- Efficient randomized algorithms for fixed precision problem of approximate Tucker decomposition
- A chiseling algorithm for low-rank Grassmann decomposition of skew-symmetric tensors
This page was built for publication: Tensor-structured sketching for constrained least squares
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5021024)
