Neural Computation, Vol 10, 1455-1480, Copyright © 1998 by The MIT Press

LETTERS

An Equivalence Between Sparse Approximation And Support Vector Machines

Federico Girosi

This article shows a relationship between two different approximation techniques: the support vector machines (SVM), proposed by V. Vapnik (1995) and a sparse approximation scheme that resembles the basis pursuit denoising algorithm (Chen, 1995; Chen, Donoho, &Saunders, 1995). SVM is a technique that can be derived from the structural risk minimization principle (Vapnik, 1982) and can be used to estimate the parameters of several different approximation schemes, including radial basis functions, algebraic and trigonometric polynomials, B-splines, and some forms of multilayer perceptrons. Basis pursuit denoising is a sparse approximation technique in which a function is reconstructed by using a small number of basis functions chosen from a large set (the dictionary). We show that if the data are noiseless, the modified version of basis pursuit denoising proposed in this article is equivalent to SVM in the following sense: if applied to the same data set, the two techniques give the same solution, which is obtained by solving the same quadratic programming problem. In the appendix, we present a derivation of the SVM technique in the framework of regularization theory, rather than statistical learning theory, establishing a connection between SVM, sparse approximation, and regularization theory.

This article has been cited by other articles:

				M. SUGIYAMA and K. SAKURAI Analytic Optimization of Shrinkage Parameters Based on Regularized Subspace Information Criterion IEICE Trans A: Fundamentals, August 1, 2006; E89-A(8): 2216 - 2225. [Abstract] [PDF]

				N. Ancona and S. Stramaglia An invariance property of predictors in kernel-induced hypothesis spaces. Neural Comput., April 1, 2006; 18(4): 749 - 759. [Abstract] [Full Text] [PDF]

				L. Paninski, J. W. Pillow, and E. P. Simoncelli Maximum Likelihood Estimation of a Stochastic Integrate-and-Fire Neural Encoding Model Neural Comput., December 1, 2004; 16(12): 2533 - 2561. [Abstract] [Full Text] [PDF]

				M. Sugiyama, M. Kawanabe, and K.-R. Muller Trading Variance Reduction with Unbiasedness: The Regularized Subspace Information Criterion for Robust Model Selection in Kernel Regression Neural Comput., May 1, 2004; 16(5): 1077 - 1104. [Abstract] [Full Text] [PDF]

				Z. Chen and S. Haykin On Different Facets of Regularization Theory Neural Comput., December 1, 2002; 14(12): 2791 - 2846. [Abstract] [Full Text]

				T. Zhang Approximation Bounds for Some Sparse Kernel Regression Algorithms Neural Comput., December 1, 2002; 14(12): 3013 - 3042. [Abstract] [Full Text]

				J.-M. Wu Natural Discriminant Analysis Using Interactive Potts Models Neural Comput., March 1, 2002; 14(3): 689 - 713. [Abstract] [Full Text]

				J. B. Gao, C. J. Harris, and S. R. Gunn On a Class of Support Vector Kernels Based on Frames in Function Hilbert Spaces Neural Comput., September 1, 2001; 13(9): 1975 - 1994. [Abstract] [Full Text] [PDF]

				B. Scholkopf, J. C. Platt, J. Shawe-Taylor, A. J. Smola, and R. C. Williamson Estimating the Support of a High-Dimensional Distribution Neural Comput., July 1, 2001; 13(7): 1443 - 1471. [Abstract] [Full Text]

				B. Schölkopf, A. J. Smola, R. C. Williamson, and P. L. Bartlett New Support Vector Algorithms Neural Comput., May 1, 2000; 12(5): 1207 - 1245. [Abstract] [Full Text]

				S.-i. Amari Natural Gradient Learning for Over- and Under-Complete Bases in ICA Neural Comput., November 15, 1999; 11(8): 1875 - 1883. [Abstract] [Full Text]