Multi-resolutive sparse approximations of d-dimensional data
Identifieur interne : 000925 ( PascalFrancis/Curation ); précédent : 000924; suivant : 000926Multi-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.
| pA |
|
|---|
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000082
Links to Exploration step
Pascal:13-0182219Le 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></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></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></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><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>1077-3142</s0></fA01><fA02 i1="01"><s0>CVIUF4</s0></fA02><fA03 i2="1"><s0>Comput. vis. image underst. : (Print)</s0></fA03><fA05><s2>117</s2></fA05><fA06><s2>4</s2></fA06><fA08 i1="01" i2="1" l="ENG"><s1>Multi-resolutive sparse approximations of d-dimensional data</s1></fA08><fA09 i1="01" i2="1" l="ENG"><s1>Discrete Geometry for Computer Imagery</s1></fA09><fA11 i1="01" i2="1"><s1>PATANE (Giuseppe)</s1></fA11><fA12 i1="01" i2="1"><s1>DEBLED-RENNESSON (Isabelle)</s1><s9>ed.</s9></fA12><fA12 i1="02" i2="1"><s1>DOMENJOUD (Eric)</s1><s9>ed.</s9></fA12><fA12 i1="03" i2="1"><s1>KERAUTRET (Bertrand)</s1><s9>ed.</s9></fA12><fA12 i1="04" i2="1"><s1>EVEN (Philippe)</s1><s9>ed.</s9></fA12><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></fA14><fA15 i1="01"><s1>LORIA (Lorraine Research Laboratory in Computer Science and its Applications), UMR 7503, Lorraine University</s1><s2>Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>2 aut.</sZ><sZ>3 aut.</sZ><sZ>4 aut.</sZ></fA15><fA20><s1>418-428</s1></fA20><fA21><s1>2013</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA43 i1="01"><s1>INIST</s1><s2>15463A</s2><s5>354000502487160100</s5></fA43><fA44><s0>0000</s0><s1>© 2013 INIST-CNRS. All rights reserved.</s1></fA44><fA45><s0>62 ref.</s0></fA45><fA47 i1="01" i2="1"><s0>13-0182219</s0></fA47><fA60><s1>P</s1></fA60><fA61><s0>A</s0></fA61><fA64 i1="01" i2="1"><s0>Computer vision and image understanding : (Print)</s0></fA64><fA66 i1="01"><s0>NLD</s0></fA66><fC01 i1="01" l="ENG"><s0>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.</s0></fC01><fC02 i1="01" i2="X"><s0>001D02A05</s0></fC02><fC02 i1="02" i2="X"><s0>001D04A04A2</s0></fC02><fC02 i1="03" i2="X"><s0>001D02B07B</s0></fC02><fC02 i1="04" i2="X"><s0>001D02A06</s0></fC02><fC03 i1="01" i2="X" l="FRE"><s0>Vision ordinateur</s0><s5>01</s5></fC03><fC03 i1="01" i2="X" l="ENG"><s0>Computer vision</s0><s5>01</s5></fC03><fC03 i1="01" i2="X" l="SPA"><s0>Visión ordenador</s0><s5>01</s5></fC03><fC03 i1="02" i2="X" l="FRE"><s0>Image tridimensionnelle</s0><s5>06</s5></fC03><fC03 i1="02" i2="X" l="ENG"><s0>Tridimensional image</s0><s5>06</s5></fC03><fC03 i1="02" i2="X" l="SPA"><s0>Imagen tridimensional</s0><s5>06</s5></fC03><fC03 i1="03" i2="X" l="FRE"><s0>Analyse image</s0><s5>07</s5></fC03><fC03 i1="03" i2="X" l="ENG"><s0>Image analysis</s0><s5>07</s5></fC03><fC03 i1="03" i2="X" l="SPA"><s0>Análisis imagen</s0><s5>07</s5></fC03><fC03 i1="04" i2="X" l="FRE"><s0>Traitement image</s0><s5>08</s5></fC03><fC03 i1="04" i2="X" l="ENG"><s0>Image processing</s0><s5>08</s5></fC03><fC03 i1="04" i2="X" l="SPA"><s0>Procesamiento imagen</s0><s5>08</s5></fC03><fC03 i1="05" i2="X" l="FRE"><s0>Représentation fonction</s0><s5>18</s5></fC03><fC03 i1="05" i2="X" l="ENG"><s0>Function representation</s0><s5>18</s5></fC03><fC03 i1="05" i2="X" l="SPA"><s0>Representación función</s0><s5>18</s5></fC03><fC03 i1="06" i2="X" l="FRE"><s0>Propriété spectrale</s0><s5>19</s5></fC03><fC03 i1="06" i2="X" l="ENG"><s0>Spectral properties</s0><s5>19</s5></fC03><fC03 i1="06" i2="X" l="SPA"><s0>Propiedad espectral</s0><s5>19</s5></fC03><fC03 i1="07" i2="X" l="FRE"><s0>Analyse n dimensionnelle</s0><s5>20</s5></fC03><fC03 i1="07" i2="X" l="ENG"><s0>Multidimensional analysis</s0><s5>20</s5></fC03><fC03 i1="07" i2="X" l="SPA"><s0>Análisis n dimensional</s0><s5>20</s5></fC03><fC03 i1="08" i2="X" l="FRE"><s0>Représentation parcimonieuse</s0><s5>23</s5></fC03><fC03 i1="08" i2="X" l="ENG"><s0>Sparse representation</s0><s5>23</s5></fC03><fC03 i1="08" i2="X" l="SPA"><s0>Representación parsimoniosa</s0><s5>23</s5></fC03><fC03 i1="09" i2="X" l="FRE"><s0>Méthode itérative</s0><s5>24</s5></fC03><fC03 i1="09" i2="X" l="ENG"><s0>Iterative method</s0><s5>24</s5></fC03><fC03 i1="09" i2="X" l="SPA"><s0>Método iterativo</s0><s5>24</s5></fC03><fC03 i1="10" i2="X" l="FRE"><s0>Classification à vaste marge</s0><s5>25</s5></fC03><fC03 i1="10" i2="X" l="ENG"><s0>Vector support machine</s0><s5>25</s5></fC03><fC03 i1="10" i2="X" l="SPA"><s0>Máquina ejemplo soporte</s0><s5>25</s5></fC03><fC03 i1="11" i2="X" l="FRE"><s0>Régularisation</s0><s5>26</s5></fC03><fC03 i1="11" i2="X" l="ENG"><s0>Regularization</s0><s5>26</s5></fC03><fC03 i1="11" i2="X" l="SPA"><s0>Regularización</s0><s5>26</s5></fC03><fC03 i1="12" i2="X" l="FRE"><s0>Approximation L1</s0><s5>27</s5></fC03><fC03 i1="12" i2="X" l="ENG"><s0>L1 approximation</s0><s5>27</s5></fC03><fC03 i1="12" i2="X" l="SPA"><s0>Aproximación L1</s0><s5>27</s5></fC03><fC03 i1="13" i2="X" l="FRE"><s0>Equation non linéaire</s0><s5>28</s5></fC03><fC03 i1="13" i2="X" l="ENG"><s0>Non linear equation</s0><s5>28</s5></fC03><fC03 i1="13" i2="X" l="SPA"><s0>Ecuación no lineal</s0><s5>28</s5></fC03><fC03 i1="14" i2="X" l="FRE"><s0>Méthode noyau</s0><s5>29</s5></fC03><fC03 i1="14" i2="X" l="ENG"><s0>Kernel method</s0><s5>29</s5></fC03><fC03 i1="14" i2="X" l="SPA"><s0>Método núcleo</s0><s5>29</s5></fC03><fC03 i1="15" i2="X" l="FRE"><s0>Espace Hilbert</s0><s5>30</s5></fC03><fC03 i1="15" i2="X" l="ENG"><s0>Hilbert space</s0><s5>30</s5></fC03><fC03 i1="15" i2="X" l="SPA"><s0>Espacio Hilbert</s0><s5>30</s5></fC03><fC03 i1="16" i2="X" l="FRE"><s0>Fonction généralisée</s0><s5>31</s5></fC03><fC03 i1="16" i2="X" l="ENG"><s0>Generalized function</s0><s5>31</s5></fC03><fC03 i1="16" i2="X" l="SPA"><s0>Función generalizada</s0><s5>31</s5></fC03><fC03 i1="17" i2="X" l="FRE"><s0>Méthode moindre carré</s0><s5>32</s5></fC03><fC03 i1="17" i2="X" l="ENG"><s0>Least squares method</s0><s5>32</s5></fC03><fC03 i1="17" i2="X" l="SPA"><s0>Método cuadrado menor</s0><s5>32</s5></fC03><fC03 i1="18" i2="X" l="FRE"><s0>Fonction base radiale</s0><s5>33</s5></fC03><fC03 i1="18" i2="X" l="ENG"><s0>Radial basis function</s0><s5>33</s5></fC03><fC03 i1="18" i2="X" l="SPA"><s0>Función radial base</s0><s5>33</s5></fC03><fC03 i1="19" i2="X" l="FRE"><s0>Matrice creuse</s0><s5>34</s5></fC03><fC03 i1="19" i2="X" l="ENG"><s0>Sparse matrix</s0><s5>34</s5></fC03><fC03 i1="19" i2="X" l="SPA"><s0>Matriz dispersa</s0><s5>34</s5></fC03><fC03 i1="20" i2="X" l="FRE"><s0>Théorie spectrale</s0><s5>35</s5></fC03><fC03 i1="20" i2="X" l="ENG"><s0>Spectral theory</s0><s5>35</s5></fC03><fC03 i1="20" i2="X" l="SPA"><s0>Teoría espectral</s0><s5>35</s5></fC03><fC03 i1="21" i2="X" l="FRE"><s0>Théorie graphe</s0><s5>36</s5></fC03><fC03 i1="21" i2="X" l="ENG"><s0>Graph theory</s0><s5>36</s5></fC03><fC03 i1="21" i2="X" l="SPA"><s0>Teoría grafo</s0><s5>36</s5></fC03><fC03 i1="22" i2="X" l="FRE"><s0>Réduction dimension</s0><s5>37</s5></fC03><fC03 i1="22" i2="X" l="ENG"><s0>Dimension reduction</s0><s5>37</s5></fC03><fC03 i1="22" i2="X" l="SPA"><s0>Reducción dimensión</s0><s5>37</s5></fC03><fC03 i1="23" i2="X" l="FRE"><s0>.</s0><s4>INC</s4><s5>82</s5></fC03><fC03 i1="24" i2="X" l="FRE"><s0>Système ordre réduit</s0><s4>CD</s4><s5>96</s5></fC03><fC03 i1="24" i2="X" l="ENG"><s0>Reduced order systems</s0><s4>CD</s4><s5>96</s5></fC03><fC03 i1="24" i2="X" l="SPA"><s0>Reducción del orden de un modelo</s0><s4>CD</s4><s5>96</s5></fC03><fN21><s1>161</s1></fN21><fN44 i1="01"><s1>OTO</s1></fN44><fN82><s1>OTO</s1></fN82></pA></standard></inist></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000925 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Curation/biblio.hfd -nk 000925 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Curation
|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. |  |