×

Spectral multidimensional scaling. (English) Zbl 1292.62078

Summary: Scientific theories describe observations by equations with a small number of parameters or dimensions. Memory and computational efficiency of dimension reduction procedures is a function of the size of the observed data. Sparse local operators that involve almost linear complexity, and faithful multiscale models with quadratic cost, make the design of dimension reduction tools a delicate balance between modeling accuracy and efficiency. Here, we propose multiscale modeling of the data at a modest computational cost. We project the classical multidimensional scaling problem into the data spectral domain. Then, embedding into a low-dimensional space is efficiently accomplished. Theoretical support and empirical evidence demonstrate that working in the natural eigenspace of the data, one could reduce the complexity while maintaining model fidelity.

MSC:

62H11 Directional data; spatial statistics
68T05 Learning and adaptive systems in artificial intelligence
58C40 Spectral theory; eigenvalue problems on manifolds
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] IEEE TRANS PAMI 11 pp 1005– (1989) · Zbl 05112286 · doi:10.1109/34.35506
[2] Drury, Journal of Cognitive Neuroscience 8 (1) pp 1– (1996) · doi:10.1162/jocn.1996.8.1.1
[3] Dale, NeuroImage 9 (2) pp 179– (1999) · doi:10.1006/nimg.1998.0395
[4] IEEE TRANS PAMI 24 pp 433– (2002) · Zbl 05111058 · doi:10.1109/34.993552
[5] IEEE TRANS PAMI 25 pp 1285– (2003) · Zbl 05112448 · doi:10.1109/TPAMI.2003.1233902
[6] 67 pp 297– (2006) · Zbl 05062691 · doi:10.1007/s11263-006-5166-3
[7] 64 pp 5– (2005) · Zbl 02244111 · doi:10.1007/s11263-005-1085-y
[8] Tenenbaum, Science 290 (5500) pp 2319– (2000) · doi:10.1126/science.290.5500.2319
[9] Kimmel, PNAS 95 (15) pp 8431– (1998) · Zbl 0908.65049 · doi:10.1073/pnas.95.15.8431
[10] Roweis, Science 290 (5500) pp 2323– (2000) · doi:10.1126/science.290.5500.2323
[11] PNAS 100 (10) pp 5591– (2003) · Zbl 1130.62337 · doi:10.1073/pnas.1031596100
[12] 21 pp 5– (2006) · Zbl 1095.68094 · doi:10.1016/j.acha.2006.04.006
[13] PNAS 102 (21) pp 7426– (2005) · doi:10.1073/pnas.0500334102
[14] COMPUT GEOM THEORY APPL 42 pp 289– (2009) · Zbl 1169.05378 · doi:10.1016/j.comgeo.2008.06.004
[15] NUMER LINEAR ALGEBRA APP 13 pp 149– (2006) · Zbl 1174.68537 · doi:10.1002/nla.475
[16] 89 pp 56– (2010) · Zbl 1477.68489 · doi:10.1007/s11263-010-0322-1
[17] 27 pp 951– (2011) · doi:10.1007/s00371-011-0629-0
[18] GEOM FUNCT ANAL 4 pp 373– (1994) · Zbl 0806.53044 · doi:10.1007/BF01896401
[19] COMP GRAPH FORUM 28 pp 1383– (2009) · Zbl 05650606 · doi:10.1111/j.1467-8659.2009.01515.x
[20] BULL AM MATH SOC 56 pp 115– (1950) · Zbl 0041.21003 · doi:10.1090/S0002-9904-1950-09369-0
[21] PROC IEEE 86 pp 2278– (1998) · doi:10.1109/5.726791
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.