Improved Analysis of the subsampled Randomized Hadamard Transform

By Joel A. Tropp. 2010

386 citations recorded by the source corpus.

This paper presents an improved analysis of a structured dimension-reduction map called the subsampled randomized Hadamard transform. This argument demonstrates that the map preserves the Euclidean geometry of an entire subspace of vectors. The new proof is much simpler than previous approaches, and it offers---for the first time---optimal constants in the estimate on the number of dimensions required for the embedding.

Subfields: Applied Mathematics, Electrical and Electronic Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Electrical and Electronic Engineering

Citations in the corpus

User-Friendly Tail Bounds for Sums of Random Matrices (2010, methodology): “See [54] for a problem where this method is effective.”
GIANT: Globally Improved Approximate Newton Method for Distributed Optimization (2017, methodology): “ ˆ 2 p m : Besides uniform sampling, other sketching methods such as leverage score sampling [7], Gaussian projection [13], Rademacher random variables [1], subsampled randomized Hadamard transform [49, 8, 21] also satisfy Assumption3. In addition, these sketching methods eliminate the dependence of”
Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions (2009, background): “1 follows from a straightforward variation of the argument in [135], which establishes equivalent bounds for a real analogue of the SRFT, called the subsampled randomized Hadamard transform (SRHT).”
LOCO: Distributing Ridge Regression with Random Projections (2014, neutral): “In more detail, it consists of a projection matrix, Π = τ/τ subs DHS [6,9] with the deﬁnitions: • S ∈ R τ × τ subs is a subsampling matrix.”
DUAL-LOCO: Distributing Statistical Estimation Using Random Projections (2015, background): “The second is an application of (cid:96) 2 penalized regression to a problem in climate science where accurate recovery of the coef-ﬁcient estimates is of primary interest.”
A Survey of Multi-View Representation Learning (2016, neutral): “[44, 58] propose a fast algorithm for CCA with a pair of tall-and-thin matrices using subsampled randomized Walsh-Hadamard transform [59], which only subsamples a small proportion of the training data points to approximate the matrix product.”
Compact Random Feature Maps (2013, methodology): “Note that while down-projection using structured random matrices is straight forward (Tropp, 2011), we need to incorporate a few novel modifications to previous structured random projection approaches before they can be used for the up-projection step (see § 3.5).”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “J. A. Tropp (2011b), ‘Improved analysis of the subsampled randomized Hadamard transform’, Adv.”
Revisiting the Nystrom Method for Improved Large-scale Machine Learning (2013, methodology): “at larger. That an SRFT with a smaller value of r 1 can be used instead is a consequence of the fact that Lemma 3 in [20] is also satised by an SRFT matrix with the given r 1; this is established in [58, 13]. The running time of this algorithm, given in the caption of the algorithm, is roughly O(ndl”
Preserving privacy between features in distributed estimation (2017, background): “k 2 R subs is the subsampled randomized Hadamard transform matrix, which admits fast matrix–vector products (Tropp, 2011).”
Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method (2012, background): “h probability at least 1¡n¡1. Proposition 3.3 results from an argument based on the matrix Chernoff inequality [Tro12, Thm. 1.1] and a union bound. A model for this type of proof appears in the paper [Tro11]. We omit the details. In contrast, if we wish to construct a paving with a nontrivial lower ”
The Expected Norm of a Sum of Independent Random Matrices: An Elementary Approach (2015, background): “These tools have already found a place in a huge number of mathematical research fields, including • numerical linear algebra [Tro11] • numerical analysis [MB14] • uncertainty quantification [CG14] • statistics [Kol11] • econometrics [CC13] • approximation theory [CDL13] • sampling theory [BG13] • m”