Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-26T04:52:00.051Z Has data issue: false hasContentIssue false
  • English
  • Français

LEAST SQUARES APPROXIMATIONS OF MEASURES VIA GEOMETRIC CONDITION NUMBERS

Part of: Classical measure theory

Published online by Cambridge University Press:  20 December 2011

Gilad Lerman  and
J. Tyler Whitehouse
Gilad Lerman
Affiliation:
School of Mathematics, University of Minnesota, 127 Vincent Hall, 206 Church St. SE, Minneapolis 55455, U.S.A. (email: [email protected])
J. Tyler Whitehouse
Affiliation:
Department of Mathematics, Vanderbilt University, 1326 Stevenson Center, Nashville 37240, U.S.A. (email: [email protected])
Get access

Abstract

For a probability measure μ on a real separable Hilbert space H, we are interested in “volume-based” approximations of the d-dimensional least squares error of μ, i.e., least squares error with respect to a best fit d-dimensional affine subspace. Such approximations are given by averaging real-valued multivariate functions which are typically scalings of squared (d+1)-volumes of (d+1)-simplices in H. Specifically, we show that such averages are comparable to the square of the d-dimensional least squares error of μ, where the comparison depends on a simple quantitative geometric property of μ. This result is a higher dimensional generalization of the elementary fact that the double integral of the squared distances between points is proportional to the variance of μ. We relate our work to two recent algorithms, one for clustering affine subspaces and the other for Monte-Carlo singular value decomposition based on volume sampling.

MSC classification

Secondary: 28A35: Measures and integrals in product spaces
Type
Research Article
Information
Mathematika , Volume 58 , Issue 1 , January 2012 , pp. 45 - 70
Copyright
Copyright © University College London 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Agarwal, S., Lim, J., Zelnik-Manor, L., Perona, P., Kriegman, D. and Belongie, S., Beyond pairwise clustering. In Proc. 2005 IEEE Computer Society Conf. Computer Vision and Pattern Recognition (CVPR’05), Vol. 2, 2005, 838–845.Google Scholar
[2]Arias-Castro, E., Chen, G. and Lerman, G., Spectral clustering based on local linear approximations. Electron. J. Stat. 5 (2011), 1537–1587.CrossRefGoogle Scholar
[3]Brand, M., A fast greedy pairwise distance clustering algorithm and its use in discovering thematic structures in large data sets. Technical Report 406, MIT Media Lab, 1996.Google Scholar
[4]Chen, G. and Lerman, G., Foundations of a multi-way spectral clustering framework for hybrid linear modelling. Found. Comput. Math. 9(5) (2009), 517–558.CrossRefGoogle Scholar
[5]Chen, G. and Lerman, G., Spectral curvature clustering (SCC). Int. J. Comput. Vis. 81(3) (2009), 317–330.CrossRefGoogle Scholar
[6]David, G. and Semmes, S., Singular integrals and rectifiable sets in ℝn: au-delà des graphes Lipschitziens. Astérisque 193 (1991), 1–145.Google Scholar
[7]Deshpande, A., Rademacher, L., Vempala, S. and Wang, G., Matrix approximation and projective clustering via volume sampling. Theory Comput. 2(12) (2006), 225–247.CrossRefGoogle Scholar
[8]Deshpande, A. and Vempala, S., Adaptive sampling and fast low-rank matrix approximation. In Approximation, Randomization and Combinatorial Optimization (Lecture Notes in Computer Science 4110), Springer (Berlin, 2006), 292–303.Google Scholar
[9]Fan, K., On a theorem of Weyl concerning eigenvalues of linear transformations. I. Proc. Natl. Acad. Sci. USA 35 (1949), 652–655.CrossRefGoogle ScholarPubMed
[10]Gohberg, I., Goldberg, S. and Krupnik, N., Traces and Determinants of Linear Operators (Operator Theory: Advances and Applications 116), Birkhäuser (Basel, 2000).CrossRefGoogle Scholar
[11]Govindu, V., A tensor decomposition for geometric grouping and segmentation. In Proc. 2005 IEEE Computer Society Conf. Computer Vision and Pattern Recognition (CVPR’05), Vol. 1, 2005, 1150–1157.Google Scholar
[12]Halmos, P. R. and Sunder, V. S., Bounded Integral Operators on L 2 Spaces (Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas] 96), Springer (Berlin, 1978).CrossRefGoogle Scholar
[13]Léger, J. C., Menger curvature and rectifiability. Ann. of Math. (2) 149 (1999), 831–869.Google Scholar
[14]Lerman, G. and Whitehouse, J. T., High-dimensional Menger-type curvatures. II. d-separation and a menagerie of curvatures. Constr. Approx. 30(3) (2009), 325–360.CrossRefGoogle Scholar
[15]Lerman, G. and Whitehouse, J. T., On d-dimensional d-semimetrics and simplex-type inequalities for high-dimensional sine functions. J. Approx. Theory 156(1) (2009), 52–81.CrossRefGoogle Scholar
[16]Lerman, G. and Whitehouse, J. T., High-dimensional Menger-type curvatures—Part I: geometric multipoles and multiscale inequalities. Rev. Mat. Iberoam. 27(2) (2011), 493–555.Google Scholar
[17]Mattila, P., Melnikov, M. and Verdera, J., The Cauchy integral, analytic capacity, and uniform rectifiability. Ann. of Math. (2) 144(1) (1996), 127–136.Google Scholar
[18]McDiarmid, C., On the method of bounded differences. In Surveys in Combinatorics, 1989 (Norwich, 1989) (London Mathematical Society Lecture Note Series 141), Cambridge University Press (Cambridge, 1989), 148–188.Google Scholar
[19]Shashua, A., Zass, R. and Hazan, T., Multi-way clustering using super-symmetric non-negative tensor factorization. In Computer Vision – ECCV 2006 (Lecture Notes in Computer Science 3954), Springer (Berlin, 2006), 595–608.CrossRefGoogle Scholar
[20]Strzelecki, P. and von der Mosel, H., Integral menger curvature for surfaces. Adv. Math. 226(3) (2011), 2233–2304.CrossRefGoogle Scholar
[21]Tolsa, X., Principal values for Riesz transforms and rectifiability. J. Funct. Anal. 254(7) (2008), 1811–1863.CrossRefGoogle Scholar
[22]Yafaev, D. R., Mathematical Scattering Theory (Translations of Mathematical Monographs 105), American Mathematical Society (Providence, RI, 1992) (translated from the Russian by J. R. Schulenberger).CrossRefGoogle Scholar