Precise expressions for random projections: Low-rank approximation and randomized Newton

• URL: http://arxiv.org/abs/2006.10653v3
• Date: Mon, 13 Jun 2022 18:13:51 GMT
• Title: Precise expressions for random projections: Low-rank approximation and randomized Newton
• Authors: Micha{\l} Derezi\'nski, Feynman Liang, Zhenyu Liao and Michael W. Mahoney
• Abstract summary: Matrix sketching has emerged as a powerful technique for performing such dimensionality reduction very efficiently. We develop techniques that provide provably accurate expressions for the expected value of random projection matrices obtained via sketching. These expressions can be used to characterize the performance of dimensionality reduction in a variety of common machine learning tasks.
• Score: 63.68433510953756
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: It is often desirable to reduce the dimensionality of a large dataset by projecting it onto a low-dimensional subspace. Matrix sketching has emerged as a powerful technique for performing such dimensionality reduction very efficiently. Even though there is an extensive literature on the worst-case performance of sketching, existing guarantees are typically very different from what is observed in practice. We exploit recent developments in the spectral analysis of random matrices to develop novel techniques that provide provably accurate expressions for the expected value of random projection matrices obtained via sketching. These expressions can be used to characterize the performance of dimensionality reduction in a variety of common machine learning tasks, ranging from low-rank approximation to iterative stochastic optimization. Our results apply to several popular sketching methods, including Gaussian and Rademacher sketches, and they enable precise analysis of these methods in terms of spectral properties of the data. Empirical results show that the expressions we derive reflect the practical performance of these sketching methods, down to lower-order effects and even constant factors.

Related papers

• Distributed Least Squares in Small Space via Sketching and Bias Reduction [0.0]
  Matrix sketching is a powerful tool for reducing the size of large data matrices. We show that these limitations can be circumvented in the distributed setting by designing sketching methods that minimize the bias of the estimator, rather than its error. In particular, we give a sparse sketching method running in optimal space and current matrix multiplication time, which recovers a nearly-unbiased least squares estimator using two passes over the data.
  arXiv  Detail & Related papers  (2024-05-08T18:16:37Z)
• Probabilistic Reduced-Dimensional Vector Autoregressive Modeling with Oblique Projections [0.7614628596146602]
  We propose a reduced-dimensional vector autoregressive model to extract low-dimensional dynamics from noisy data. An optimal oblique decomposition is derived for the best predictability regarding prediction error covariance. The superior performance and efficiency of the proposed approach are demonstrated using data sets from a synthesized Lorenz system and an industrial process from Eastman Chemical.
  arXiv  Detail & Related papers  (2024-01-14T05:38:10Z)
• An evaluation framework for dimensionality reduction through sectional curvature [59.40521061783166]
  In this work, we aim to introduce the first highly non-supervised dimensionality reduction performance metric. To test its feasibility, this metric has been used to evaluate the performance of the most commonly used dimension reduction algorithms. A new parameterized problem instance generator has been constructed in the form of a function generator.
  arXiv  Detail & Related papers  (2023-03-17T11:59:33Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition [14.453949553412821]
  We develop a theoretical framework for obtaining sharp guarantees on the convergence rate of sketch-and-project methods. We show that the convergence rate improves at least linearly with the sketch size, and even faster when the data matrix exhibits certain spectral decays. Our experiments support the theory and demonstrate that even extremely sparse sketches exhibit the convergence properties predicted by our framework.
  arXiv  Detail & Related papers  (2022-08-20T03:11:13Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. We show that the Gaussian sketching matrix can be drastically sparsified, significantly reducing the computational cost of sketching. We prove that Newton-LESS enjoys nearly the same problem-independent local convergence rate as Gaussian embeddings.
  arXiv  Detail & Related papers  (2021-07-15T17:33:05Z)
• Deep Dimension Reduction for Supervised Representation Learning [51.10448064423656]
  We propose a deep dimension reduction approach to learning representations with essential characteristics. The proposed approach is a nonparametric generalization of the sufficient dimension reduction method. We show that the estimated deep nonparametric representation is consistent in the sense that its excess risk converges to zero.
  arXiv  Detail & Related papers  (2020-06-10T14:47:43Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.