
-
Previous Article
A Bayesian nonparametric test for conditional independence
- FoDS Home
- This Issue
-
Next Article
Topological reconstruction of sub-cellular motion with Ensemble Kalman velocimetry
Hierarchical approximations for data reduction and learning at multiple scales
Data Intensive Studies Center, Tufts University, Medford, MA, 02155, USA |
This paper describes a hierarchical learning strategy for generating sparse representations of multivariate datasets. The hierarchy arises from approximation spaces considered at successively finer scales. A detailed analysis of stability, convergence and behavior of error functionals associated with the approximations are presented, along with a well chosen set of applications. Results show the performance of the approach as a data reduction mechanism for both synthetic (univariate and multivariate) and a real dataset (geo-spatial). The sparse representation generated is shown to efficiently reconstruct data and minimize error in prediction. The approach is also shown to generalize well to unseen samples, extending its prospective application to statistical learning problems.
References:
[1] |
N. I. Achieser, Theory of Approximation, Frederick Ungar Publishing Co., New York, 1956. |
[2] |
W. K. Allard, G. Chen and M. Maggioni,
Multi-scale geometric methods for data setsⅡ: Geometric multi-resolution analysis, Appl. Comput. Harmon. Anal., 32 (2012), 435-462.
doi: 10.1016/j.acha.2011.08.001. |
[3] |
N. Aronszajn,
Theory of reproducing kernels, Trans. Amer. Math. Soc., 68 (1950), 337-404.
doi: 10.1090/S0002-9947-1950-0051437-7. |
[4] |
F. Bellocchio, N. Borghese, S. Ferrari and V. Piuri, Kernel regression in HRBF networks for surface reconstruction, 2008 IEEE International Workshop on Haptic Audio Visual Environments and Games, (2008), 160–165.
doi: 10.1109/HAVE.2008.4685317. |
[5] |
A. Bermanis, A. Averbuch and R. R. Coifman,
Multiscale data sampling and function extension, Appl. Comput. Harmon. Anal., 34 (2013), 15-29.
doi: 10.1016/j.acha.2012.03.002. |
[6] |
A. Bermanis, G. Wolf and A. Averbuch,
Diffusion-based kernel methods on euclidean metric measure spaces, Appl. Comput. Harmon. Anal., 41 (2016), 190-213.
doi: 10.1016/j.acha.2015.07.005. |
[7] |
B. Bohn, J. Garcke and M. Griebel,
A sparse grid based method for generative dimensionality reduction of high-dimensional data, J. Comput. Phys., 309 (2016), 1-17.
doi: 10.1016/j.jcp.2015.12.033. |
[8] |
N. A. Borghese and S. Ferrari,
Hierarchical rbf networks and local parameters estimate, Neurocomputing, 19 (1998), 259-283.
|
[9] |
C. Boutsidis, M. W. Mahoney and P. Drineas, An improved approximation algorithm for the column subset selection problem, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, (2009), 968–977. |
[10] |
W. L. Briggs, V. E. Henson and S. F. McCormick, A Multigrid Tutorial, 2nd edition, SIAM, 2000.
doi: 10.1137/1.9780898719505. |
[11] |
M. D. Buhmann, Radial Basis Functions: Theory and Implementations, Vol. 12, Cambridge university press, 2003.
doi: 10.1017/CBO9780511543241.![]() ![]() ![]() |
[12] |
J. C. Carr, W. R. Fright and R. K. Beatson,
Surface interpolation with radial basis functions for medical imaging, IEEE Transactions on Medical Imaging, 16 (1997), 96-107.
doi: 10.1109/42.552059. |
[13] |
G. Chen, A. V. Little and M. Maggioni, Multi-resolution geometric analysis for data in high dimensions, in Excursions in Harmonic Analysis, Springer, 1 (2013), 259–285.
doi: 10.1007/978-0-8176-8376-4_13. |
[14] |
E. W. Cheney, Introduction to Approximation Theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. |
[15] |
W. Cheney and W. Light, A Course in Approximation Theory, Vol. 101, American Mathematical Society, 2009.
doi: 10.1090/gsm/101. |
[16] |
C. H. Chou, B. H. Kuo and F. Chang,
The generalized condensed nearest neighbor rule as a data reduction method, 18th International Conference on Pattern Recognition, 2 (2006), 556-559.
|
[17] |
A. Çivril and M. Magdon-Ismail,
On selecting a maximum volume sub-matrix of a matrix and related problems, Theoret. Comput. Sci., 410 (2009), 4801-4811.
doi: 10.1016/j.tcs.2009.06.018. |
[18] |
R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner and S. W. Zucker,
Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps, Proceedings of the National Academy of Sciences, 102 (2005), 7426-7431.
|
[19] |
R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner and S. W. Zucker,
Geometric diffusions as a tool for harmonic analysis and structure definition of data: Multiscale methods, Proceedings of the National Academy of Sciences, 102 (2005), 7432-7437.
|
[20] |
R. R. Coifman and M. Maggioni,
Diffusion wavelets, Appl. Comput. Harmon. Anal., 21 (2006), 53-94.
doi: 10.1016/j.acha.2006.04.004. |
[21] |
I. Daubechies, Ten Lectures on Wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, 61. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992.
doi: 10.1137/1.9781611970104. |
[22] |
S. De Marchi and R. Schaback,
Stability of kernel-based interpolation, Adv. Comput. Math., 32 (2010), 155-161.
doi: 10.1007/s10444-008-9093-4. |
[23] |
A. Deshpande and S. Vempala, Adaptive sampling and fast low-rank matrix approximation, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer, (2006), 292–303.
doi: 10.1007/11830924_28. |
[24] |
G. E. Fasshauer and J. G. Zhang, Preconditioning of radial basis function interpolation systems via accelerated iterated approximate moving least squares approximation, in Progress on Meshless Methods, Springer, (2009), 57–75.
doi: 10.1007/978-1-4020-8821-6_4. |
[25] |
S. Ferrari, F. Bellocchio, V. Piuri and N. A. Borghese,
A hierarchical rbf online learning algorithm for real-time 3-d scanner, IEEE Transactions on Neural Networks, 21 (2009), 275-285.
|
[26] |
S. Ferrari, M. Maggioni and N. A. Borghese,
Multiscale approximation with hierarchical radial basis functions networks, IEEE Transactions on Neural Networks, 15 (2004), 178-188.
doi: 10.1109/TNN.2003.811355. |
[27] |
M. S Floater and A. Iske,
Multistep scattered data interpolation using compactly supported radial basis functions, J. Comput. Appl. Math., 73 (1996), 65-78.
doi: 10.1016/0377-0427(96)00035-0. |
[28] |
T. E. Fricker, J. E. Oakley and N. M. Urban,
Multivariate Gaussian process emulators with nonseparable covariance structures, Technometrics, 55 (2013), 47-56.
doi: 10.1080/00401706.2012.715835. |
[29] |
M. Galun, R. Basri and I. Yavneh,
Review of methods inspired by algebraic-multigrid for data and image analysis applications, Numer. Math. Theory Methods Appl., 8 (2015), 283-312.
doi: 10.4208/nmtma.2015.w14si. |
[30] |
M. Gavish, B. Nadler and R. R. Coifman, Multiscale wavelets on trees, graphs and high dimensional data: Theory and applications to semi supervised learning, ICML, (2010), 367–374. |
[31] |
M. Griebel and A. Hullmann, A sparse grid based generative topographic mapping for the dimensionality reduction of high-dimensional data, Modeling, Simulation and Optimization of Complex Processes-HPSC, Springer, (2012), 51–62. |
[32] |
M. Gu and J. O. Berger,
Parallel partial Gaussian process emulation for computer models with massive output, Ann. Appl. Stat., 10 (2016), 1317-1347.
doi: 10.1214/16-AOAS934. |
[33] |
A. Iske,
Scattered data approximation by positive definite kernel functions, Rend. Semin. Mat. Univ. Politec. Torino, 69 (2011), 217-246.
|
[34] |
P. Koumoutsakos,
Multiscale flow simulations using particles, Annu. Rev. Fluid Mech., 37 (2005), 457-487.
doi: 10.1146/annurev.fluid.37.061903.175753. |
[35] |
E. Kreyszig, Introductory Functional Analysis with Applications, Vol. 1, John Wiley & Sons, New York-London-Sydney, 1978. |
[36] |
D. Kushnir, M. Galun and A. Brandt,
Efficient multilevel eigensolvers with applications to data analysis tasks, IEEE Transactions on Pattern Analysis and Machine Intelligence, 32 (2009), 1377-1391.
doi: 10.1109/TPAMI.2009.147. |
[37] |
T. Lane and C. E. Brodley, Temporal sequence learning and data reduction for anomaly detection, CCS '98: Proceedings of the 5th ACM Conference on Computer and communications Security, (1998), 150–158.
doi: 10.1145/288090.288122. |
[38] |
M. Maggioni, J. C. Bremer Jr, R. R. Coifman and A. D. Szlam, Biorthogonal diffusion wavelets for multiscale representation on manifolds and graphs, in Wavelets XI, International Society for Optics and Photonics, 5914, (2005), 59141M.
doi: 10.1117/12.616909. |
[39] |
S. G. Mallat,
A theory for multiresolution signal decomposition: The wavelet representation, IEEE Transactions on Pattern Analysis & Machine Intelligence, 11 (1989), 674-693.
|
[40] |
S. Paul, M. Magdon-Ismail and P. Drineas, Column selection via adaptive sampling, in Advances in Neural Information Processing Systems, (2015), 406–414. |
[41] |
M. J. D. Powell, Approximation Theory and Methods, Cambridge university press, 1981.
![]() ![]() |
[42] |
A. Quarteroni and A. Veneziani,
Analysis of a geometrical multiscale model based on the coupling of ODEs and PDEs for blood flow simulations, Multiscale Model. Simul., 1 (2003), 173-195.
doi: 10.1137/S1540345902408482. |
[43] |
C. E. Rasmussen and C. K. I Williams, Gaussian Process for Machine Learning Adaptive Computation and Machine Learning, MIT Press, Cambridge, MA, 2006.
![]() ![]() |
[44] |
E. Sadrfaridpour, S. Jeereddy, K. Kennedy, A. Luckow, T. Razzaghi and I. Safro, Algebraic multigrid support vector machines, preprint, (2016), arXiv: 1611.05487. |
[45] |
L. Shih, J. D. Rennie, Y. H. Chang and D. R. Karger, Text bundling: Statistics based data-reduction, in Proceedings of the 20th International Conference on Machine Learning (ICML-03), (2003), 696–703. |
[46] |
K. Stüben, A review of algebraic multigrid, in Numerical Analysis: Historical Developments in the 20th Century, Elsevier, (2001), 331–359. |
[47] |
S. Surjanovic and D. Bingham, Virtual Library of Simulation Experiments: Test Functions and Datasets, Retrieved January 23, 2019, from http://www.sfu.ca/ ssurjano. |
[48] |
A. D. Szlam, M. Maggioni, R. R. Coifman and J. C. Bremer Jr, Diffusion-driven multiscale analysis on manifolds and graphs: top-down and bottom-up constructions, in Wavelets XI, International Society for Optics and Photonics, 5914 (2005), 59141D. |
[49] |
J. T. Vogelstein, Y. Park, T. Ohyama, R. A. Kerr, J. W. Truman, C. E. Priebe and M. Zlatic,
Discovery of brainwide neural-behavioral maps via multiscale unsupervised structure learning, Science, 344 (2014), 386-392.
|
[50] |
H. Wendland, Scattered Data Approximation, Cambridge Monographs on Applied and Computational Mathematics, Vol. 17, Cambridge university press, 2005.
![]() ![]() |
[51] |
Q. Wu, T. Xia, C. Chen, H.-Y. S. Lin, H. Wang and Y. Yu,
Hierarchical tensor approximation of multi-dimensional visual data, IEEE Transactions on Visualization and Computer Graphics, 14 (2007), 186-199.
|
show all references
References:
[1] |
N. I. Achieser, Theory of Approximation, Frederick Ungar Publishing Co., New York, 1956. |
[2] |
W. K. Allard, G. Chen and M. Maggioni,
Multi-scale geometric methods for data setsⅡ: Geometric multi-resolution analysis, Appl. Comput. Harmon. Anal., 32 (2012), 435-462.
doi: 10.1016/j.acha.2011.08.001. |
[3] |
N. Aronszajn,
Theory of reproducing kernels, Trans. Amer. Math. Soc., 68 (1950), 337-404.
doi: 10.1090/S0002-9947-1950-0051437-7. |
[4] |
F. Bellocchio, N. Borghese, S. Ferrari and V. Piuri, Kernel regression in HRBF networks for surface reconstruction, 2008 IEEE International Workshop on Haptic Audio Visual Environments and Games, (2008), 160–165.
doi: 10.1109/HAVE.2008.4685317. |
[5] |
A. Bermanis, A. Averbuch and R. R. Coifman,
Multiscale data sampling and function extension, Appl. Comput. Harmon. Anal., 34 (2013), 15-29.
doi: 10.1016/j.acha.2012.03.002. |
[6] |
A. Bermanis, G. Wolf and A. Averbuch,
Diffusion-based kernel methods on euclidean metric measure spaces, Appl. Comput. Harmon. Anal., 41 (2016), 190-213.
doi: 10.1016/j.acha.2015.07.005. |
[7] |
B. Bohn, J. Garcke and M. Griebel,
A sparse grid based method for generative dimensionality reduction of high-dimensional data, J. Comput. Phys., 309 (2016), 1-17.
doi: 10.1016/j.jcp.2015.12.033. |
[8] |
N. A. Borghese and S. Ferrari,
Hierarchical rbf networks and local parameters estimate, Neurocomputing, 19 (1998), 259-283.
|
[9] |
C. Boutsidis, M. W. Mahoney and P. Drineas, An improved approximation algorithm for the column subset selection problem, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, (2009), 968–977. |
[10] |
W. L. Briggs, V. E. Henson and S. F. McCormick, A Multigrid Tutorial, 2nd edition, SIAM, 2000.
doi: 10.1137/1.9780898719505. |
[11] |
M. D. Buhmann, Radial Basis Functions: Theory and Implementations, Vol. 12, Cambridge university press, 2003.
doi: 10.1017/CBO9780511543241.![]() ![]() ![]() |
[12] |
J. C. Carr, W. R. Fright and R. K. Beatson,
Surface interpolation with radial basis functions for medical imaging, IEEE Transactions on Medical Imaging, 16 (1997), 96-107.
doi: 10.1109/42.552059. |
[13] |
G. Chen, A. V. Little and M. Maggioni, Multi-resolution geometric analysis for data in high dimensions, in Excursions in Harmonic Analysis, Springer, 1 (2013), 259–285.
doi: 10.1007/978-0-8176-8376-4_13. |
[14] |
E. W. Cheney, Introduction to Approximation Theory, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. |
[15] |
W. Cheney and W. Light, A Course in Approximation Theory, Vol. 101, American Mathematical Society, 2009.
doi: 10.1090/gsm/101. |
[16] |
C. H. Chou, B. H. Kuo and F. Chang,
The generalized condensed nearest neighbor rule as a data reduction method, 18th International Conference on Pattern Recognition, 2 (2006), 556-559.
|
[17] |
A. Çivril and M. Magdon-Ismail,
On selecting a maximum volume sub-matrix of a matrix and related problems, Theoret. Comput. Sci., 410 (2009), 4801-4811.
doi: 10.1016/j.tcs.2009.06.018. |
[18] |
R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner and S. W. Zucker,
Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps, Proceedings of the National Academy of Sciences, 102 (2005), 7426-7431.
|
[19] |
R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner and S. W. Zucker,
Geometric diffusions as a tool for harmonic analysis and structure definition of data: Multiscale methods, Proceedings of the National Academy of Sciences, 102 (2005), 7432-7437.
|
[20] |
R. R. Coifman and M. Maggioni,
Diffusion wavelets, Appl. Comput. Harmon. Anal., 21 (2006), 53-94.
doi: 10.1016/j.acha.2006.04.004. |
[21] |
I. Daubechies, Ten Lectures on Wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, 61. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992.
doi: 10.1137/1.9781611970104. |
[22] |
S. De Marchi and R. Schaback,
Stability of kernel-based interpolation, Adv. Comput. Math., 32 (2010), 155-161.
doi: 10.1007/s10444-008-9093-4. |
[23] |
A. Deshpande and S. Vempala, Adaptive sampling and fast low-rank matrix approximation, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer, (2006), 292–303.
doi: 10.1007/11830924_28. |
[24] |
G. E. Fasshauer and J. G. Zhang, Preconditioning of radial basis function interpolation systems via accelerated iterated approximate moving least squares approximation, in Progress on Meshless Methods, Springer, (2009), 57–75.
doi: 10.1007/978-1-4020-8821-6_4. |
[25] |
S. Ferrari, F. Bellocchio, V. Piuri and N. A. Borghese,
A hierarchical rbf online learning algorithm for real-time 3-d scanner, IEEE Transactions on Neural Networks, 21 (2009), 275-285.
|
[26] |
S. Ferrari, M. Maggioni and N. A. Borghese,
Multiscale approximation with hierarchical radial basis functions networks, IEEE Transactions on Neural Networks, 15 (2004), 178-188.
doi: 10.1109/TNN.2003.811355. |
[27] |
M. S Floater and A. Iske,
Multistep scattered data interpolation using compactly supported radial basis functions, J. Comput. Appl. Math., 73 (1996), 65-78.
doi: 10.1016/0377-0427(96)00035-0. |
[28] |
T. E. Fricker, J. E. Oakley and N. M. Urban,
Multivariate Gaussian process emulators with nonseparable covariance structures, Technometrics, 55 (2013), 47-56.
doi: 10.1080/00401706.2012.715835. |
[29] |
M. Galun, R. Basri and I. Yavneh,
Review of methods inspired by algebraic-multigrid for data and image analysis applications, Numer. Math. Theory Methods Appl., 8 (2015), 283-312.
doi: 10.4208/nmtma.2015.w14si. |
[30] |
M. Gavish, B. Nadler and R. R. Coifman, Multiscale wavelets on trees, graphs and high dimensional data: Theory and applications to semi supervised learning, ICML, (2010), 367–374. |
[31] |
M. Griebel and A. Hullmann, A sparse grid based generative topographic mapping for the dimensionality reduction of high-dimensional data, Modeling, Simulation and Optimization of Complex Processes-HPSC, Springer, (2012), 51–62. |
[32] |
M. Gu and J. O. Berger,
Parallel partial Gaussian process emulation for computer models with massive output, Ann. Appl. Stat., 10 (2016), 1317-1347.
doi: 10.1214/16-AOAS934. |
[33] |
A. Iske,
Scattered data approximation by positive definite kernel functions, Rend. Semin. Mat. Univ. Politec. Torino, 69 (2011), 217-246.
|
[34] |
P. Koumoutsakos,
Multiscale flow simulations using particles, Annu. Rev. Fluid Mech., 37 (2005), 457-487.
doi: 10.1146/annurev.fluid.37.061903.175753. |
[35] |
E. Kreyszig, Introductory Functional Analysis with Applications, Vol. 1, John Wiley & Sons, New York-London-Sydney, 1978. |
[36] |
D. Kushnir, M. Galun and A. Brandt,
Efficient multilevel eigensolvers with applications to data analysis tasks, IEEE Transactions on Pattern Analysis and Machine Intelligence, 32 (2009), 1377-1391.
doi: 10.1109/TPAMI.2009.147. |
[37] |
T. Lane and C. E. Brodley, Temporal sequence learning and data reduction for anomaly detection, CCS '98: Proceedings of the 5th ACM Conference on Computer and communications Security, (1998), 150–158.
doi: 10.1145/288090.288122. |
[38] |
M. Maggioni, J. C. Bremer Jr, R. R. Coifman and A. D. Szlam, Biorthogonal diffusion wavelets for multiscale representation on manifolds and graphs, in Wavelets XI, International Society for Optics and Photonics, 5914, (2005), 59141M.
doi: 10.1117/12.616909. |
[39] |
S. G. Mallat,
A theory for multiresolution signal decomposition: The wavelet representation, IEEE Transactions on Pattern Analysis & Machine Intelligence, 11 (1989), 674-693.
|
[40] |
S. Paul, M. Magdon-Ismail and P. Drineas, Column selection via adaptive sampling, in Advances in Neural Information Processing Systems, (2015), 406–414. |
[41] |
M. J. D. Powell, Approximation Theory and Methods, Cambridge university press, 1981.
![]() ![]() |
[42] |
A. Quarteroni and A. Veneziani,
Analysis of a geometrical multiscale model based on the coupling of ODEs and PDEs for blood flow simulations, Multiscale Model. Simul., 1 (2003), 173-195.
doi: 10.1137/S1540345902408482. |
[43] |
C. E. Rasmussen and C. K. I Williams, Gaussian Process for Machine Learning Adaptive Computation and Machine Learning, MIT Press, Cambridge, MA, 2006.
![]() ![]() |
[44] |
E. Sadrfaridpour, S. Jeereddy, K. Kennedy, A. Luckow, T. Razzaghi and I. Safro, Algebraic multigrid support vector machines, preprint, (2016), arXiv: 1611.05487. |
[45] |
L. Shih, J. D. Rennie, Y. H. Chang and D. R. Karger, Text bundling: Statistics based data-reduction, in Proceedings of the 20th International Conference on Machine Learning (ICML-03), (2003), 696–703. |
[46] |
K. Stüben, A review of algebraic multigrid, in Numerical Analysis: Historical Developments in the 20th Century, Elsevier, (2001), 331–359. |
[47] |
S. Surjanovic and D. Bingham, Virtual Library of Simulation Experiments: Test Functions and Datasets, Retrieved January 23, 2019, from http://www.sfu.ca/ ssurjano. |
[48] |
A. D. Szlam, M. Maggioni, R. R. Coifman and J. C. Bremer Jr, Diffusion-driven multiscale analysis on manifolds and graphs: top-down and bottom-up constructions, in Wavelets XI, International Society for Optics and Photonics, 5914 (2005), 59141D. |
[49] |
J. T. Vogelstein, Y. Park, T. Ohyama, R. A. Kerr, J. W. Truman, C. E. Priebe and M. Zlatic,
Discovery of brainwide neural-behavioral maps via multiscale unsupervised structure learning, Science, 344 (2014), 386-392.
|
[50] |
H. Wendland, Scattered Data Approximation, Cambridge Monographs on Applied and Computational Mathematics, Vol. 17, Cambridge university press, 2005.
![]() ![]() |
[51] |
Q. Wu, T. Xia, C. Chen, H.-Y. S. Lin, H. Wang and Y. Yu,
Hierarchical tensor approximation of multi-dimensional visual data, IEEE Transactions on Visualization and Computer Graphics, 14 (2007), 186-199.
|














Algorithm 1 Hierarchical approach |
1: INPUT:
Hyperparameters: Dataset: Prediction points: 2: OUTPUT: Convergence Scale: Sparse Representation ( Predictions: 3: Initialize: 4: while 5: Compute covariance kernel: [ 6: Compute numerical Rank: [ 7: Remove sampling Bias: [ 8: Generate permutation information: [ 9: Produce bases at scale s: 10: Subset the sparse representation in 11: Compute projection coordinate: [ 12: Generate approximation at s: [ 13: If 14: Update scale: [ 15: end while 16: Compute bases for prediction at 17: Predict: |
Algorithm 1 Hierarchical approach |
1: INPUT:
Hyperparameters: Dataset: Prediction points: 2: OUTPUT: Convergence Scale: Sparse Representation ( Predictions: 3: Initialize: 4: while 5: Compute covariance kernel: [ 6: Compute numerical Rank: [ 7: Remove sampling Bias: [ 8: Generate permutation information: [ 9: Produce bases at scale s: 10: Subset the sparse representation in 11: Compute projection coordinate: [ 12: Generate approximation at s: [ 13: If 14: Update scale: [ 15: end while 16: Compute bases for prediction at 17: Predict: |
Training time (s) | Prediction time (s) | |||||
50 | 4.61e-03 | 3.25e-02 | 100 | 1.47e-02 | 7.22e-02 | |
100 | 9.25e-03 | 1.40e-02 | 200 | 4.15e-02 | 3.09e-01 | |
150 | 1.60e-02 | 2.93e-02 | 300 | 6.21e-02 | 5.82e-01 | |
200 | 2.55e-02 | 5.63e-02 | 400 | 8.18e-02 | 1.08 | |
250 | 3.77e-02 | 9.29e-02 | 500 | 1.12e-01 | 1.81 | |
300 | 5.64e-02 | 1.25e-01 | 600 | 1.31e-01 | 2.38 | |
350 | 6.51e-02 | 1.93e-01 | 700 | 1.48e-01 | 3.56 | |
400 | 8.36e-02 | 2.21e-01 | 800 | 1.70e-01 | 4.15 | |
50 | 5.68e-03 | 9.21e-03 | 100 | 2.17e-02 | 8.35e-02 | |
100 | 1.35e-02 | 1.49e-02 | 200 | 6.75e-02 | 3.00e-01 | |
150 | 2.86e-02 | 2.80e-02 | 300 | 1.53e-01 | 6.36e-01 | |
200 | 5.28e-02 | 5.27e-02 | 400 | 2.71e-01 | 1.07 | |
250 | 8.97e-02 | 8.94e-02 | 500 | 4.09e-01 | 1.81 | |
300 | 1.15e-01 | 1.23e-01 | 600 | 5.91e-01 | 2.29 | |
350 | 1.86e-01 | 1.75e-01 | 700 | 8.06e-01 | 3.52 | |
400 | 2.12e-01 | 2.17e-01 | 800 | 1.08 | 4.10 | |
900 | 8.39e-01 | 7.98e-01 | 1225 | 3.13 | 8.67 | |
1600 | 4.19 | 6.40 | 2025 | 5.29 | 2.14e+01 | |
2500 | 2.76e+01 | 2.67e+01 | 3025 | 7.91 | 3.47e+01 | |
3600 | 7.19e+01 | 8.24e+01 | 4225 | 1.16e+01 | 4.95e+01 | |
4900 | 1.72e+02 | 1.99e+02 | 5625 | 1.59e+01 | 6.87e+01 | |
6400 | 3.84e+02 | 4.44e+02 | 7225 | 2.05e+01 | 8.73e+01 | |
8100 | 7.71e+02 | 8.88e+02 | 9025 | 2.75e+01 | 1.08e+02 | |
10000 | 1.44e+03 | 1.88e+03 | 11025 | 3.27e+01 | 2.32e+02 | |
900 | 1.42 | 8.70e-01 | 1225 | 4.10 | 1.53e+01 | |
1600 | 6.94 | 8.68 | 2025 | 1.05e+01 | 3.21e+01 | |
2500 | 3.51e+01 | 3.44e+01 | 3025 | 2.25e+01 | 5.44e+01 | |
3600 | 1.27e+02 | 1.27e+02 | 4225 | 5.25e+01 | 1.32e+02 | |
4900 | 2.94e+02 | 2.95e+02 | 5625 | 8.78e+01 | 2.02e+02 | |
6400 | 7.90e+02 | 7.94e+02 | 7225 | 1.52e+02 | 3.96e+02 | |
8100 | 1.49e+03 | 1.49e+03 | 9025 | 2.24e+02 | 5.37e+02 | |
10000 | 2.69e+03 | 2.69e+03 | 11025 | 3.37e+02 | 6.90e+02 |
Training time (s) | Prediction time (s) | |||||
50 | 4.61e-03 | 3.25e-02 | 100 | 1.47e-02 | 7.22e-02 | |
100 | 9.25e-03 | 1.40e-02 | 200 | 4.15e-02 | 3.09e-01 | |
150 | 1.60e-02 | 2.93e-02 | 300 | 6.21e-02 | 5.82e-01 | |
200 | 2.55e-02 | 5.63e-02 | 400 | 8.18e-02 | 1.08 | |
250 | 3.77e-02 | 9.29e-02 | 500 | 1.12e-01 | 1.81 | |
300 | 5.64e-02 | 1.25e-01 | 600 | 1.31e-01 | 2.38 | |
350 | 6.51e-02 | 1.93e-01 | 700 | 1.48e-01 | 3.56 | |
400 | 8.36e-02 | 2.21e-01 | 800 | 1.70e-01 | 4.15 | |
50 | 5.68e-03 | 9.21e-03 | 100 | 2.17e-02 | 8.35e-02 | |
100 | 1.35e-02 | 1.49e-02 | 200 | 6.75e-02 | 3.00e-01 | |
150 | 2.86e-02 | 2.80e-02 | 300 | 1.53e-01 | 6.36e-01 | |
200 | 5.28e-02 | 5.27e-02 | 400 | 2.71e-01 | 1.07 | |
250 | 8.97e-02 | 8.94e-02 | 500 | 4.09e-01 | 1.81 | |
300 | 1.15e-01 | 1.23e-01 | 600 | 5.91e-01 | 2.29 | |
350 | 1.86e-01 | 1.75e-01 | 700 | 8.06e-01 | 3.52 | |
400 | 2.12e-01 | 2.17e-01 | 800 | 1.08 | 4.10 | |
900 | 8.39e-01 | 7.98e-01 | 1225 | 3.13 | 8.67 | |
1600 | 4.19 | 6.40 | 2025 | 5.29 | 2.14e+01 | |
2500 | 2.76e+01 | 2.67e+01 | 3025 | 7.91 | 3.47e+01 | |
3600 | 7.19e+01 | 8.24e+01 | 4225 | 1.16e+01 | 4.95e+01 | |
4900 | 1.72e+02 | 1.99e+02 | 5625 | 1.59e+01 | 6.87e+01 | |
6400 | 3.84e+02 | 4.44e+02 | 7225 | 2.05e+01 | 8.73e+01 | |
8100 | 7.71e+02 | 8.88e+02 | 9025 | 2.75e+01 | 1.08e+02 | |
10000 | 1.44e+03 | 1.88e+03 | 11025 | 3.27e+01 | 2.32e+02 | |
900 | 1.42 | 8.70e-01 | 1225 | 4.10 | 1.53e+01 | |
1600 | 6.94 | 8.68 | 2025 | 1.05e+01 | 3.21e+01 | |
2500 | 3.51e+01 | 3.44e+01 | 3025 | 2.25e+01 | 5.44e+01 | |
3600 | 1.27e+02 | 1.27e+02 | 4225 | 5.25e+01 | 1.32e+02 | |
4900 | 2.94e+02 | 2.95e+02 | 5625 | 8.78e+01 | 2.02e+02 | |
6400 | 7.90e+02 | 7.94e+02 | 7225 | 1.52e+02 | 3.96e+02 | |
8100 | 1.49e+03 | 1.49e+03 | 9025 | 2.24e+02 | 5.37e+02 | |
10000 | 2.69e+03 | 2.69e+03 | 11025 | 3.37e+02 | 6.90e+02 |
[1] |
Tyrus Berry, Timothy Sauer. Consistent manifold representation for topological data analysis. Foundations of Data Science, 2019, 1 (1) : 1-38. doi: 10.3934/fods.2019001 |
[2] |
Changming Song, Yun Wang. Nonlocal latent low rank sparse representation for single image super resolution via self-similarity learning. Inverse Problems and Imaging, 2021, 15 (6) : 1347-1362. doi: 10.3934/ipi.2021017 |
[3] |
Jiang Xie, Junfu Xu, Celine Nie, Qing Nie. Machine learning of swimming data via wisdom of crowd and regression analysis. Mathematical Biosciences & Engineering, 2017, 14 (2) : 511-527. doi: 10.3934/mbe.2017031 |
[4] |
Andreas Chirstmann, Qiang Wu, Ding-Xuan Zhou. Preface to the special issue on analysis in machine learning and data science. Communications on Pure and Applied Analysis, 2020, 19 (8) : i-iii. doi: 10.3934/cpaa.2020171 |
[5] |
Kanghui Guo and Demetrio Labate. Sparse shearlet representation of Fourier integral operators. Electronic Research Announcements, 2007, 14: 7-19. doi: 10.3934/era.2007.14.7 |
[6] |
Georg Vossen, Stefan Volkwein. Model reduction techniques with a-posteriori error analysis for linear-quadratic optimal control problems. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 465-485. doi: 10.3934/naco.2012.2.465 |
[7] |
Ning Zhang, Qiang Wu. Online learning for supervised dimension reduction. Mathematical Foundations of Computing, 2019, 2 (2) : 95-106. doi: 10.3934/mfc.2019008 |
[8] |
Norikazu Saito. Error analysis of a conservative finite-element approximation for the Keller-Segel system of chemotaxis. Communications on Pure and Applied Analysis, 2012, 11 (1) : 339-364. doi: 10.3934/cpaa.2012.11.339 |
[9] |
Rua Murray. Approximation error for invariant density calculations. Discrete and Continuous Dynamical Systems, 1998, 4 (3) : 535-557. doi: 10.3934/dcds.1998.4.535 |
[10] |
Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete and Continuous Dynamical Systems - S, 2021, 14 (8) : 3043-3054. doi: 10.3934/dcdss.2020463 |
[11] |
Eduardo Casas, Mariano Mateos, Arnd Rösch. Finite element approximation of sparse parabolic control problems. Mathematical Control and Related Fields, 2017, 7 (3) : 393-417. doi: 10.3934/mcrf.2017014 |
[12] |
Jian-Bing Zhang, Yi-Xin Sun, De-Chuan Zhan. Multiple-instance learning for text categorization based on semantic representation. Big Data & Information Analytics, 2017, 2 (1) : 69-75. doi: 10.3934/bdia.2017009 |
[13] |
Hang Xu, Song Li. Analysis non-sparse recovery for relaxed ALASSO. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4055-4068. doi: 10.3934/cpaa.2020179 |
[14] |
Jules Guillot, Emmanuel Frénod, Pierre Ailliot. Physics informed model error for data assimilation. Discrete and Continuous Dynamical Systems - S, 2022 doi: 10.3934/dcdss.2022059 |
[15] |
Shuhua Xu, Fei Gao. Weighted two-phase supervised sparse representation based on Gaussian for face recognition. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1385-1400. doi: 10.3934/dcdss.2015.8.1385 |
[16] |
Ralf Banisch, Carsten Hartmann. A sparse Markov chain approximation of LQ-type stochastic control problems. Mathematical Control and Related Fields, 2016, 6 (3) : 363-389. doi: 10.3934/mcrf.2016007 |
[17] |
Eduardo Casas, Boris Vexler, Enrique Zuazua. Sparse initial data identification for parabolic PDE and its finite element approximations. Mathematical Control and Related Fields, 2015, 5 (3) : 377-399. doi: 10.3934/mcrf.2015.5.377 |
[18] |
Xiaoying Han, Jinglai Li, Dongbin Xiu. Error analysis for numerical formulation of particle filter. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1337-1354. doi: 10.3934/dcdsb.2015.20.1337 |
[19] |
Anders C. Hansen. A theoretical framework for backward error analysis on manifolds. Journal of Geometric Mechanics, 2011, 3 (1) : 81-111. doi: 10.3934/jgm.2011.3.81 |
[20] |
Walter Allegretto, Yanping Lin, Ningning Yan. A posteriori error analysis for FEM of American options. Discrete and Continuous Dynamical Systems - B, 2006, 6 (5) : 957-978. doi: 10.3934/dcdsb.2006.6.957 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]