# Non-PSD Matrix Sketching with Applications to Regression and Optimization

arXiv: https://arxiv.org/abs/2106.08544 · HTML: https://mlsanity.com/paper/2106.08544/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 56 references that are in the map.
- First posted on arXiv 16 Jun 2021.

## Builds on (most cited first, 20 of 20)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information](https://mlsanity.com/paper/1708.07164/) (2017)
- [Exact and Inexact Subsampled Newton Methods for Optimization](https://mlsanity.com/paper/1609.08502/) (2016)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study](https://mlsanity.com/paper/1708.07827/) (2017)
- [Convergence rates of sub-sampled Newton methods](https://mlsanity.com/paper/1508.02810/) (2015)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Sub-sampled Newton Methods with Non-uniform Sampling](https://mlsanity.com/paper/1607.00559/) (2016)
- [Inexact Non-Convex Newton-Type Methods](https://mlsanity.com/paper/1802.06925/) (2018)
- [Ridge Regression and Provable Deterministic Ridge Leverage Score Sampling](https://mlsanity.com/paper/1803.06010/) (2018)
- [Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems](https://mlsanity.com/paper/2006.14015/) (2020)
- [Tight Bounds for ℓp Oblivious Subspace Embeddings](https://mlsanity.com/paper/1801.04414/) (2018)
- [On Sketching Quadratic Forms](https://mlsanity.com/paper/1511.06099/) (2015)
- [trlib: A vector-free implementation of the GLTR method for iterative solution of the trust region problem](https://mlsanity.com/paper/1611.04718/) (2016)
- [An inexact subsampled proximal Newton-type method for large-scale machine learning](https://mlsanity.com/paper/1708.08552/) (2017)

## Abstract (arXiv)

A variety of dimensionality reduction techniques have been applied for computations involving large matrices. The underlying matrix is randomly compressed into a smaller one, while approximately retaining many of its original properties. As a result, much of the expensive computation can be performed on the small matrix. The sketching of positive semidefinite (PSD) matrices is well understood, but there are many applications where the related matrices are not PSD, including Hessian matrices in non-convex optimization and covariance matrices in regression applications involving complex numbers. In this paper, we present novel dimensionality reduction methods for non-PSD matrices, as well as their ``square-roots", which involve matrices with complex entries. We show how these techniques can be used for multiple downstream tasks. In particular, we show how to use the proposed matrix sketching techniques for both convex and non-convex optimization, ℓp-regression for every 1 ≤ p ≤ ∞, and vector-matrix-vector queries.