Efficient Kernel Machines Using the Improved Fast Gauss Transform

Abstract

The computation and memory required for kernel machines with N training samples is at least O(N 2). Such a complexity is significant even for moderate size problems and is prohibitive for large datasets. We present an approximation technique based on the improved fast Gauss transform to reduce the computation to O(N). We also give an error bound for the approximation, and provide experimental results on the UCI datasets. 1

Keywords

ComputationGaussKernel (algebra)Computer scienceAlgorithmApproximation errorArtificial intelligenceMathematicsDiscrete mathematics

Affiliated Institutions

Related Publications

Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements

Mark Rudelson , Roman Vershynin

This paper proves best known guarantees for exact reconstruction of a sparse signal f from few non-adaptive universal linear measurements. We consider Fourier measurements (rand...

2006 230 citations

Improved time bounds for near-optimal sparse Fourier representations

Anna C. Gilbert , S. Muthukrishnan , Michael Strauss

•We study the problem of finding a Fourier representation R of m terms for a given discrete signal A of length N. The Fast Fourier Transform (FFT) ca...

2005 Proceedings of SPIE, the Internationa... 212 citations

Uncertainty principles and ideal atomic decomposition

David L. Donoho , Xiaoming Huo

Suppose a discrete-time signal S(t), 0/spl les/t<N, is a superposition of atoms taken from a combined time-frequency dictionary made of spike sequences 1/sub {t=/spl tau/}/ and ...

2001 IEEE Transactions on Information Theory 1960 citations

Compressed sensing

David L. Donoho

Suppose x is an unknown vector in Ropfm (a digital image or signal); we plan to measure n general linear functionals of x and then reconstruct. If x is known to be compressible ...

2004 17126 citations

Compressed sensing

David L. Donoho

Suppose x is an unknown vector in Ropf m (a digital image or signal); we pla...

2006 IEEE Transactions on Information Theory 22524 citations

Publication Info

Year: 2004
Type: article
Volume: 17
Pages: 1561-1568
Citations: 128
Access: Closed

External Links

Citation Metrics

128

OpenAlex

Cite This

APA Style

                            
                                    Changjiang Yang, 
                                
                                    Ramani Duraiswami, 
                                
                                    Larry S. Davis
                                
                            (2004). 
                            Efficient Kernel Machines Using the Improved Fast Gauss Transform. 
                            
                            , 17
                            
                            , 1561-1568.