An Equivalence Between Sparse Approximation and Support Vector Machines
In the first part of this paper we show a similarity between the principle of Structural Risk Minimization Principle (SRM) (Vapnik, 1982) and the idea of Sparse Approximation, as defined in (Chen, Donoho and Saunders, 1995) and Olshausen and Field (1996). Then we focus on two specific (approxi...
| Main Author: | |
|---|---|
| Language: | en_US |
| Published: |
2004
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/7289 |
| _version_ | 1811077911506059264 |
|---|---|
| author | Girosi, Federico |
| author_facet | Girosi, Federico |
| author_sort | Girosi, Federico |
| collection | MIT |
| description | In the first part of this paper we show a similarity between the principle of Structural Risk Minimization Principle (SRM) (Vapnik, 1982) and the idea of Sparse Approximation, as defined in (Chen, Donoho and Saunders, 1995) and Olshausen and Field (1996). Then we focus on two specific (approximate) implementations of SRM and Sparse Approximation, which have been used to solve the problem of function approximation. For SRM we consider the Support Vector Machine technique proposed by V. Vapnik and his team at AT&T Bell Labs, and for Sparse Approximation we consider a modification of the Basis Pursuit De-Noising algorithm proposed by Chen, Donoho and Saunders (1995). We show that, under certain conditions, these two techniques are equivalent: they give the same solution and they require the solution of the same quadratic programming problem. |
| first_indexed | 2024-09-23T10:50:15Z |
| id | mit-1721.1/7289 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:50:15Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | mit-1721.1/72892019-04-15T00:40:29Z An Equivalence Between Sparse Approximation and Support Vector Machines Girosi, Federico Support Vector Machines Sparse Approximation Sparse Coding Reproducing Kernel Hilbert Spaces In the first part of this paper we show a similarity between the principle of Structural Risk Minimization Principle (SRM) (Vapnik, 1982) and the idea of Sparse Approximation, as defined in (Chen, Donoho and Saunders, 1995) and Olshausen and Field (1996). Then we focus on two specific (approximate) implementations of SRM and Sparse Approximation, which have been used to solve the problem of function approximation. For SRM we consider the Support Vector Machine technique proposed by V. Vapnik and his team at AT&T Bell Labs, and for Sparse Approximation we consider a modification of the Basis Pursuit De-Noising algorithm proposed by Chen, Donoho and Saunders (1995). We show that, under certain conditions, these two techniques are equivalent: they give the same solution and they require the solution of the same quadratic programming problem. 2004-10-22T20:17:52Z 2004-10-22T20:17:52Z 1997-05-01 AIM-1606 CBCL-147 http://hdl.handle.net/1721.1/7289 en_US AIM-1606 CBCL-147 16 p. 305230 bytes 497486 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Support Vector Machines Sparse Approximation Sparse Coding Reproducing Kernel Hilbert Spaces Girosi, Federico An Equivalence Between Sparse Approximation and Support Vector Machines |
| title | An Equivalence Between Sparse Approximation and Support Vector Machines |
| title_full | An Equivalence Between Sparse Approximation and Support Vector Machines |
| title_fullStr | An Equivalence Between Sparse Approximation and Support Vector Machines |
| title_full_unstemmed | An Equivalence Between Sparse Approximation and Support Vector Machines |
| title_short | An Equivalence Between Sparse Approximation and Support Vector Machines |
| title_sort | equivalence between sparse approximation and support vector machines |
| topic | Support Vector Machines Sparse Approximation Sparse Coding Reproducing Kernel Hilbert Spaces |
| url | http://hdl.handle.net/1721.1/7289 |
| work_keys_str_mv | AT girosifederico anequivalencebetweensparseapproximationandsupportvectormachines AT girosifederico equivalencebetweensparseapproximationandsupportvectormachines |