Multi-resolutive sparse approximations of d-dimensional data
Identifieur interne : 001710 ( Main/Exploration ); précédent : 001709; suivant : 001711Multi-resolutive sparse approximations of d-dimensional data
Auteurs : Giuseppe Patane [Italie]Source :
- Computer vision and image understanding : (Print) [ 1077-3142 ] ; 2013.
Descripteurs français
- Pascal (Inist)
- Vision ordinateur, Image tridimensionnelle, Analyse image, Traitement image, Représentation fonction, Propriété spectrale, Analyse n dimensionnelle, Représentation parcimonieuse, Méthode itérative, Classification à vaste marge, Régularisation, Approximation L1, Equation non linéaire, Méthode noyau, Espace Hilbert, Fonction généralisée, Méthode moindre carré, Fonction base radiale, Matrice creuse, Théorie spectrale, Théorie graphe, Réduction dimension, ., Système ordre réduit.
English descriptors
- KwdEn :
- Computer vision, Dimension reduction, Function representation, Generalized function, Graph theory, Hilbert space, Image analysis, Image processing, Iterative method, Kernel method, L1 approximation, Least squares method, Multidimensional analysis, Non linear equation, Radial basis function, Reduced order systems, Regularization, Sparse matrix, Sparse representation, Spectral properties, Spectral theory, Tridimensional image, Vector support machine.
Abstract
This paper proposes an iterative computation of sparse representations of functions defined on d, which exploits a formulation of the sparsification problem equivalent to Support Vector Machine and based on Tikhonov regularization. Through this equivalent formulation, the sparsification reduces to an approximation problem with a Tikhonov regularizer, which selects the null coefficients of the resulting approximation. The proposed multi-resolutive sparsification achieves a different resolution in the approximation of the input data through a hierarchy of nested approximation spaces. The idea behind our approach is to combine a smooth and strictly convex approximation of the l1-norm with Tikhonov regularization and iterative solvers of linear/non-linear equations. Firstly, the iterative sparsification scheme is introduced in a Reproducing Kernel Hilbert Space with respect to its native norm. Then, the sparsification is generalized to arbitrary function spaces using the least-squares norm and radial basis functions. Finally, the discrete sparsification is derived using the eigendecomposition and the spectral properties of sparse matrices; in this case, the computational cost is O(nlogn), with n number of input points. Assuming that the data is supported on a (d - 1 )-dimensional manifold, we derive a variant of the sparsification scheme that guarantees the smoothness of the solution in the ambient and intrinsic space by using spectral graph theory and manifold learning techniques. Finally, we discuss the multi-resolutive approximation of d-dimensional data such as signals, images, and 3D shapes.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000082
- to stream PascalFrancis, to step Curation: 000925
- to stream PascalFrancis, to step Checkpoint: 000056
- to stream Main, to step Merge: 001727
- to stream Main, to step Curation: 001710
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Multi-resolutive sparse approximations of d-dimensional data</title><author><name sortKey="Patane, Giuseppe" sort="Patane, Giuseppe" uniqKey="Patane G" first="Giuseppe" last="Patane">Giuseppe Patane</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Consiglio Nazionale delle Ricerche, Istituto di Matematica Applicata e Tecnologie Informatiche</s1><s2>Genova</s2><s3>ITA</s3><sZ>1 aut.</sZ></inist:fA14><country>Italie</country><wicri:noRegion>Genova</wicri:noRegion></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">13-0182219</idno><date when="2013">2013</date><idno type="stanalyst">PASCAL 13-0182219 INIST</idno><idno type="RBID">Pascal:13-0182219</idno><idno type="wicri:Area/PascalFrancis/Corpus">000082</idno><idno type="wicri:Area/PascalFrancis/Curation">000925</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000056</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000056</idno><idno type="wicri:doubleKey">1077-3142:2013:Patane G:multi:resolutive:sparse</idno><idno type="wicri:Area/Main/Merge">001727</idno><idno type="wicri:Area/Main/Curation">001710</idno><idno type="wicri:Area/Main/Exploration">001710</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Multi-resolutive sparse approximations of d-dimensional data</title><author><name sortKey="Patane, Giuseppe" sort="Patane, Giuseppe" uniqKey="Patane G" first="Giuseppe" last="Patane">Giuseppe Patane</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Consiglio Nazionale delle Ricerche, Istituto di Matematica Applicata e Tecnologie Informatiche</s1><s2>Genova</s2><s3>ITA</s3><sZ>1 aut.</sZ></inist:fA14><country>Italie</country><wicri:noRegion>Genova</wicri:noRegion></affiliation></author></analytic><series><title level="j" type="main">Computer vision and image understanding : (Print)</title><title level="j" type="abbreviated">Comput. vis. image underst. : (Print)</title><idno type="ISSN">1077-3142</idno><imprint><date when="2013">2013</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Computer vision and image understanding : (Print)</title><title level="j" type="abbreviated">Comput. vis. image underst. : (Print)</title><idno type="ISSN">1077-3142</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Computer vision</term><term>Dimension reduction</term><term>Function representation</term><term>Generalized function</term><term>Graph theory</term><term>Hilbert space</term><term>Image analysis</term><term>Image processing</term><term>Iterative method</term><term>Kernel method</term><term>L1 approximation</term><term>Least squares method</term><term>Multidimensional analysis</term><term>Non linear equation</term><term>Radial basis function</term><term>Reduced order systems</term><term>Regularization</term><term>Sparse matrix</term><term>Sparse representation</term><term>Spectral properties</term><term>Spectral theory</term><term>Tridimensional image</term><term>Vector support machine</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Vision ordinateur</term><term>Image tridimensionnelle</term><term>Analyse image</term><term>Traitement image</term><term>Représentation fonction</term><term>Propriété spectrale</term><term>Analyse n dimensionnelle</term><term>Représentation parcimonieuse</term><term>Méthode itérative</term><term>Classification à vaste marge</term><term>Régularisation</term><term>Approximation L1</term><term>Equation non linéaire</term><term>Méthode noyau</term><term>Espace Hilbert</term><term>Fonction généralisée</term><term>Méthode moindre carré</term><term>Fonction base radiale</term><term>Matrice creuse</term><term>Théorie spectrale</term><term>Théorie graphe</term><term>Réduction dimension</term><term>.</term><term>Système ordre réduit</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">This paper proposes an iterative computation of sparse representations of functions defined on <sup>d</sup>, which exploits a formulation of the sparsification problem equivalent to Support Vector Machine and based on Tikhonov regularization. Through this equivalent formulation, the sparsification reduces to an approximation problem with a Tikhonov regularizer, which selects the null coefficients of the resulting approximation. The proposed multi-resolutive sparsification achieves a different resolution in the approximation of the input data through a hierarchy of nested approximation spaces. The idea behind our approach is to combine a smooth and strictly convex approximation of the l<sub>1</sub>-norm with Tikhonov regularization and iterative solvers of linear/non-linear equations. Firstly, the iterative sparsification scheme is introduced in a Reproducing Kernel Hilbert Space with respect to its native norm. Then, the sparsification is generalized to arbitrary function spaces using the least-squares norm and radial basis functions. Finally, the discrete sparsification is derived using the eigendecomposition and the spectral properties of sparse matrices; in this case, the computational cost is O(nlogn), with n number of input points. Assuming that the data is supported on a (d - 1 )-dimensional manifold, we derive a variant of the sparsification scheme that guarantees the smoothness of the solution in the ambient and intrinsic space by using spectral graph theory and manifold learning techniques. Finally, we discuss the multi-resolutive approximation of d-dimensional data such as signals, images, and 3D shapes.</div></front></TEI><affiliations><list><country><li>Italie</li></country></list><tree><country name="Italie"><noRegion><name sortKey="Patane, Giuseppe" sort="Patane, Giuseppe" uniqKey="Patane G" first="Giuseppe" last="Patane">Giuseppe Patane</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001710 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001710 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Pascal:13-0182219
|texte= Multi-resolutive sparse approximations of d-dimensional data
}}
| This area was generated with Dilib version V0.6.33. |  |