An Equivalence Between Sparse Approximation and Support Vector Machines

By Federico Girosi. 1998

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.

How researchers see this paper

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

Citations in the corpus

Fastfood: Approximate Kernel Expansions in Loglinear Time (2014, background): “There exists a rich body of literature on Reproducing Kernel Hilbert Spaces (RKHS) (Aronszajn, 1944; Wahba, 1990; Micchelli, 1986) and one may show that estimators using norms in feature space as penalty are equivalent to estimators using smoothness in an RKHS (Girosi, 1998; Smola et al., 1998a).”
Sparse Representation of Sounds in the Unanesthetized Auditory Cortex (2008, background): “Sparse representations have become increasingly important in statistical machine learning [71].”
Kernel Partial Least Squares Regression in Reproducing Kernel Hilbert Space (2002, background): “The common aim of support vector machines, regularization networks, Gaussian processes and spline methods (Vapnik, 1998, Girosi, 1998, Williams, 1998, Wahba, 1990, Cristianini and Shawe-Taylor, 2000) is to address the poor generalization properties of existing nonlinear regression techniques.”
Splines in Higher Order TV Regularization (2006, background): “, Hyman and Shashkov (1997). However, operators of higher order were considered in image processing, e.”
Advances in Large Margin Classifiers (2000, methodology): “It can be shown [Girosi, 1998] that this technique is equivalent to SVMR in the following sense: the two techniques give the same solution, which is obtained by solving the same quadratic programming problem.”
Weighted least squares support vector machines: robustness and sparse approximation (2002, background): “An equivalence has also been proven between sparse approximation and SVM’s [3,9].”
Robust Regression and Lasso (2008, background): “Substantial research regarding sparsity properties of Lasso can be found in the literature (cf [6, 7, 8, 9, 17, 18, 19, 20] an d many others).”
Feature Selection via Concave Minimization and Support Vector Machines (1998, methodology): “In the support vector machine approach [27, 7, 1, 10, 24, 28], in addition to minimizing the weighted sum of distances of misclassi ed points to the bounding planes, we also maximize the distance between the two bounding planes that generate the separating plane.”
Iterative kernel principal component analysis for image modeling (2005, background): “…capabilities (the associated RKHS is dense in the space of continuous functions, cf. [45]), its translation invariance, and its desirable regularization properties: It can be shown to correspond to a smoothness regularizer which penalizes derivatives of all orders (see, e.g., [16], [42]).”
Large-Scale Bayesian Logistic Regression for Text Categorization (2007, methodology): “Since then, the use of constraints or penalties based on the absolute values of coefficients has been used to achieve sparseness in logistic regression and many other data-fitting tasks (Girosi 1998; Tipping 2001; Figueiredo and Jain 2001; Figueiredo 2003; Efron, Hastie, Johnstone, and Tibshirani 20”
Learning the Kernel Function via Regularization (2005, background): “Such a function representation for learning the functionf is central for many diverse applications of kernel-based algorithms in Machine Learning.”
Input space versus feature space in kernel-based methods (1999, methodology): “2) Selection via Penalization: We next consider a method for enforcing sparseness which is inspired by shrinkage penalizers (cf., [ 13 ]).”
Value Regularization and Fenchel Duality (2007, methodology): “In Girosi (1998), an “equivalence” between a certain sparse approximation problem and a modified form of SVM regression is developed.”
Evolutionary Pursuit and Its Application to Face Recognition (2000, methodology): “A worthwhile direction for future research is to explore the role th at EP can play to further support the equivalence between sparse approximation and Support Vect or Machines (SVM) using the regularization theory [16].”