Projection-Cost-Preserving Sketches: Proof Strategies and Constructions

• URL: http://arxiv.org/abs/2004.08434v1
• Date: Fri, 17 Apr 2020 19:56:46 GMT
• Title: Projection-Cost-Preserving Sketches: Proof Strategies and Constructions
• Authors: Cameron Musco and Christopher Musco
• Abstract summary: A projection-cost-preserving sketch is a matrix approximation which, for a given parameter $k$, approximately preserves the distance of the target matrix to all $k$-dimensional subspaces. Our goal is to simplify the presentation of proof techniques introduced in [CEM+15] and [CMM17] so that they can serve as a guide for future work.
• Score: 34.38258632113394
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this note we illustrate how common matrix approximation methods, such as random projection and random sampling, yield projection-cost-preserving sketches, as introduced in [FSS13, CEM+15]. A projection-cost-preserving sketch is a matrix approximation which, for a given parameter $k$, approximately preserves the distance of the target matrix to all $k$-dimensional subspaces. Such sketches have applications to scalable algorithms for linear algebra, data science, and machine learning. Our goal is to simplify the presentation of proof techniques introduced in [CEM+15] and [CMM17] so that they can serve as a guide for future work. We also refer the reader to [CYD19], which gives a similar simplified exposition of the proof covered in Section 2.

Related papers

• Isotropic Gaussian Processes on Finite Spaces of Graphs [71.26737403006778]
  We propose a principled way to define Gaussian process priors on various sets of unweighted graphs. We go further to consider sets of equivalence classes of unweighted graphs and define the appropriate versions of priors thereon. Inspired by applications in chemistry, we illustrate the proposed techniques on a real molecular property prediction task in the small data regime.
  arXiv  Detail & Related papers  (2022-11-03T10:18:17Z)
• Asymmetric compressive learning guarantees with applications to quantized sketches [15.814495790111323]
  We present a framework to train audio event classification on large-scale datasets. We study the relaxation where this map is allowed to be different for each phase. We then instantiate this framework to the setting of quantized sketches, by proving that the LPD indeed holds for binary sketch contributions.
  arXiv  Detail & Related papers  (2021-04-20T15:37:59Z)
• Accumulations of Projections--A Unified Framework for Random Sketches in Kernel Ridge Regression [12.258887270632869]
  Building a sketch of an n-by-n empirical kernel matrix is a common approach to accelerate the computation of many kernel methods. We propose a unified framework of constructing sketching methods in kernel ridge regression.
  arXiv  Detail & Related papers  (2021-03-06T05:02:17Z)
• Learning-Augmented Sketches for Hessians [54.97773807211337]
  We show how to design learned sketches for the Hessian in the context of second order methods. We show empirically that learned sketches, compared with their "non-learned" counterparts, improve the approximation accuracy for important problems.
  arXiv  Detail & Related papers  (2021-02-24T14:50:59Z)
• Learning the Positions in CountSketch [51.15935547615698]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work we propose the first learning algorithm that also optimize the locations of the non-zero entries. We show this algorithm gives better accuracy for low rank approximation than previous work, and apply it to other problems such as $k$-means clustering for the first time.
  arXiv  Detail & Related papers  (2020-07-20T05:06:29Z)
• Localized sketching for matrix multiplication and ridge regression [29.61816941867831]
  We consider sketched approximate matrix multiplication and ridge regression in the novel setting of localized sketching. We show that, under mild conditions, block diagonal sketching matrices require only O(stable rank / epsilon2) and $O( stat. dim. epsilon)$ total sample complexity for matrix multiplication and ridge regression.
  arXiv  Detail & Related papers  (2020-03-20T04:25:32Z)
• Holistically-Attracted Wireframe Parsing [123.58263152571952]
  This paper presents a fast and parsimonious parsing method to detect a vectorized wireframe in an input image with a single forward pass. The proposed method is end-to-end trainable, consisting of three components: (i) line segment and junction proposal generation, (ii) line segment and junction matching, and (iii) line segment and junction verification.
  arXiv  Detail & Related papers  (2020-03-03T17:43:57Z)
• 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.