NDLI: The Fast Cauchy Transform and Faster Robust Linear Regression

Please wait, while we are loading the content...

The Fast Cauchy Transform and Faster Robust Linear Regression

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Drineas, Petros Mahoney, Michael W. Meng, Xiangrui Woodruff, David P. Magdon-Ismail, Malik Clarkson, Kenneth L.
Copyright Year	2016
Abstract	We provide fast algorithms for overconstrained $\ell_p$ regression and related problems: for an $n\times d$ input matrix $A$ and vector $b\in\mathbb{R}^n$, in $O(nd\log n)$ time we reduce the problem $\min_{x\in\mathbb{R}^d} \\|Ax-b\\|_p$ to the same problem with input matrix $\tilde A$ of dimension $s \times d$ and corresponding $\tilde b$ of dimension $s\times 1$. Here, $\tilde A$ and $\tilde b$ are a coreset for the problem, consisting of sampled and rescaled rows of $A$ and $b$; and $s$ is independent of $n$ and polynomial in $d$. Our results improve on the best previous algorithms when $n\gg d$ for all $p\in [1,\infty)$ except $p=2$; in particular, they improve the $O(nd^{1.376+})$ running time of Sohler and Woodruff [Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, 2011, pp. 755--764] for $p=1$, which uses asymptotically fast matrix multiplication, and the $O(nd^5\log n)$ time of Dasgupta et al. [SIAM J. Comput., 38 (2009), pp. 2060--2078] for general $p$, which uses ellipsoidal rounding. We also provide a suite of improved results for finding well-conditioned bases via ellipsoidal rounding, illustrating tradeoffs between running time and conditioning quality, including a one-pass conditioning algorithm for general $\ell_p$ problems. To complement this theory, we provide a detailed empirical evaluation of implementations of our algorithms for $p=1$, comparing them with several related algorithms. Among other things, our empirical results clearly show that, in the asymptotic regime, the theory is a very good guide to the practical performance of these algorithms. Our algorithms use our faster constructions of well-conditioned bases for $\ell_p$ spaces and, for $p=1$, a fast subspace embedding of independent interest that we call the Fast Cauchy transform: a distribution over matrices $\Pi: \mathbb{R}^n\mapsto \mathbb{R}^{O(d\log d)}$, found obliviously to $A$, that approximately preserves the $\ell_1$ norms, that is, with large probability, simultaneously for all $x$, $\\|Ax\\|_1 \approx \\|\Pi Ax\\|_1$, with distortion $O(d^{2+\eta} )$, for an arbitrarily small constant $\eta>0$; and, moreover, $\Pi A$ can be computed in $O(nd\log d)$ time. The techniques underlying our Fast Cauchy transform include Fast Johnson--Lindenstrauss transforms, low-coherence matrices, and rescaling by Cauchy random variables.
Starting Page	763
Ending Page	810
Page Count	48
File Format	PDF
ISSN	00975397
DOI	10.1137/140963698
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3 (Special Section on the Fifty-Fourth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013))
Volume Number	45
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2016-06-15
Access Restriction	Subscribed
Subject Keyword	Cauchy transform subspace embedding randomized algorithms robust regression Randomized algorithms
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The fast cauchy transform and faster robust linear regression.

The Fast Cauchy Transform and Faster Robust Linear Regression

The Fast Cauchy Transform and faster robust linear regression (2013)

A Subspace Embedding Method in Norm via Fast Cauchy Transform

Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression

OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings

Subspace Embedding and Linear Regression with Orlicz Norm

Iterative randomized robust linear regression

OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings

The Fast Cauchy Transform and Faster Robust Linear Regression

Similar Documents

The fast cauchy transform and faster robust linear regression.

The Fast Cauchy Transform and Faster Robust Linear Regression

The Fast Cauchy Transform and faster robust linear regression (2013)

A Subspace Embedding Method in Norm via Fast Cauchy Transform

Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression

OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings

Subspace Embedding and Linear Regression with Orlicz Norm

Iterative randomized robust linear regression

OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings

The Fast Cauchy Transform and Faster Robust Linear Regression