×
Tropp, Joel A.

Improved analysis of the subsampled randomized Hadamard transform. (English) Zbl 1232.15029

Adv. Adapt. Data Anal. 3, No. 1-2, 115-126 (2011).
This paper present an improved analysis of a structured dimension-reduction map called subsampled randomized Hadamard transform (SRHT). The new argument indicates that the SRHT preserves the Euclidean geometry of an entire space of vectors, which is essential for the SRHT to be used in algorithms for randomized linear algebra. The proof is much simpler than the previous approaches and it offers for the first time optimal constants in the estimate on the number of dimensions required for the embedding.
Reviewer: Xiangqian Guo (Zhengzhou)

Cited in 47 Documents

MSC:

15B52 Random matrices (algebraic aspects)
15B34 Boolean and Hadamard matrices
15A04 Linear transformations, semilinear transformations
65F30 Other matrix algorithms (MSC2010)

Keywords:

dimension reduction; numerical linear algebra; random matrix; Walsh-Hadamard matrix
PDF BibTeX XML Cite
\textit{J. A. Tropp}, Adv. Adapt. Data Anal. 3, No. 1--2, 115--126 (2011; Zbl 1232.15029)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat

References:

[1] Ailon N., SIAM J. Comput. 31 pp 302–
[2] Ahslwede R., IEEE Trans. Inform. Theory 48 pp 569–
[3] DOI: 10.1137/090771806 · Zbl 1269.65043
[4] DOI: 10.1080/01621459.1963.10500830
[5] DOI: 10.1090/conm/026/737400 · Zbl 0539.46017
[6] DOI: 10.1051/ps:1997103 · Zbl 0869.60013
[7] Ledoux M., The Concentration of Measure Phenomenon (2001) · Zbl 0995.60002
[8] DOI: 10.1017/CBO9780511814075
[9] Rudelson M., J. Assoc. Comput. Mach. 54 pp 19–
[10] DOI: 10.1016/j.acha.2007.09.001 · Zbl 1143.15026
[11] DOI: 10.1016/j.acha.2007.12.002 · Zbl 1155.65035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.