Article

Efficient subspace approximation algorithms

Authors:

Nariankadu D. Shyamalkumar,

Kasturi VaradarajanAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 532 - 540

Published: 07 January 2007 Publication History

Abstract

Confronted with high-dimensional data arising from either word-document count, global climate patterns or any one of the myriad other sources, most scientific approaches extract a good low-dimensional summary. This desire to reduce dimensionality may be seen as a consequence of Occam's Razor, and the scientific methodologies we have in mind include those from data mining and statistics.

References

[1]

P. Agarwal, S. Har-Peled, and K. Varadarajan, Geometric approximation via coresets, in J. Goodman, J. Pach, and E. Welzl (Eds), Combinatorial and Computational Geometry, Cambridge University Press, 2005.

[2]

M. Bǎdoiu and P. Indyk, Fast approximation algorithms for the hyperplane fitting problem, Manuscript, 2006.

[3]

M. Bǎdoiu, S. Har-Peled, and P. Indyk, Approximate clustering via core-sets, in Proc. 34th Annu. ACM Sympos. Theory Comput., pp. 250--257, 2002.

Digital Library

[4]

A. Brieden, Geometric optimization problems likely not contained in apx, DCG, 28(2) (2002), pp. 201--209.

[5]

R. Chandrasekharan and A. Tamir, Algebraic optimization: the Fermat-Weber location problem, Mathematical Programming, 46 (1990), pp. 219--224.

Digital Library

[6]

K. Clarkson, Subgradient and sampling algorithms for L ₁ regression, In Proceedings of SODA 2005.

Digital Library

[7]

A. Deshpande, L. Rademacher, S. Vempala, and G. Wang, Matrix approximation and projective clustering via volume sampling, in Proceedings of SODA 2006.

Digital Library

[8]

A. Deshpande and S. Vempala, Adaptive sampling and fast low-rank matrix approximation, Proceedings of RANDOM 2006.

Digital Library

[9]

J. M. Diaz-Banez, J. A. Mesa, and A. Schobel, Continuous location of dimensional structures, European Journal of Operations Research, 152 (2004), pp. 22--44.

[10]

P. Drineas, M. .W. Mahoney, and S. Muthukrishnan, Sampling algorithms for L ₂ regression and applications, In Proceedings of SODA 2005.

Digital Library

[11]

P. Drineas, M. .W. Mahoney, and S. Muthukrishnan, Subspace sampling and relative error matrix approximation: column-based methods, Proceedings of RANDOM 2006.

Digital Library

[12]

U. Faigle, W. Kern, and M. Streng, Note on the computational complexity of j-radii of polytopes in Rⁿ, Mathematical Programming, 73 (1996), pp. 1--5.

[13]

D. Feldman, A. Fiat, and M. Sharir, Coresets for weighted facilities and their applications, Proceedings of FOCS 2006.

Digital Library

[14]

A. Frieze, R. Kannan, and S. Vempala, Fast Monte-Carlo algorithms for finding low rank approximations, J. ACM, 51(6) (2004), pp. 1025--1041.

Digital Library

[15]

P. Gritzmann and V. Klee, Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces, Math. Program., 59 (1993), pp. 163--213.

Digital Library

[16]

P. Gritzmann and V. Klee, On the complexity of some basic problems in computational convexity: I. containment problems, Discrete Math., 136 (1994), pp. 129--174.

Digital Library

[17]

S. Har-Peled, How to get close to the median shape, in Proc. ACM Symp. Comput. Geom. (2006).

Digital Library

[18]

S. Har-Peled, Low rank matrix approximation in linear time, Manuscript (2006).

[19]

S. Har-Peled and K. R. Varadarajan, Projective clustering in high dimensions using core-sets, in Proc. 18th Annu. ACM Sympos. Comput. Geom. (2002), pp. 312--318.

Digital Library

[20]

S. Har-Peled and K. Varadarajan, High-Dimensional Shape Fitting in Linear Time, Discrete & Computational Geometry, 32(2) (2004), pp. 269--288.

Digital Library

[21]

N. M. Korneenko and H. Martini, Hyperplane approximation and related topics, in New Trends in Discrete and Computational Geometry, Springer-Verlag, New York, 1993.

[22]

H. Martini, Minsum k-flats of finite point sets in R^d, Studies in Locational Analysis, 7 (1994), pp. 123--129.

[23]

N. Megiddo, On the complexity of some geometric problems in unbounded dimension, J. Symb. Comput., 10 (1990), pp. 327--334.

Digital Library

[24]

R. Panigrahy, Minimum enclosing polytope in high dimensions, in arXiv.org, cs.CG/0407020.

[25]

S. Roweis, L. Saul, Nonlinear dimensionality reduction by locally linear embedding, Science, 290 (2000), pp. 2323--26.

[26]

T. Sarlos, Improved Approximation algorithms for large matrices via random projections, Proceedings of FOCS 2006.

Digital Library

[27]

J. Tenenbaum, V. de Silva and J. Langford, A global geometric framework for nonlinear dimensionality reduction, Science, 290 (2000), pp. 2319--23.

[28]

K. R. Varadarajan, S. Venkatesh, and J. Zhang, Approximating the radii of point sets in high dimensions, in Proc. 43th Annu. IEEE Sympos. Found. Comput. Sci., 2002.

Digital Library

[29]

Y. Ye and J. Zhang, An improved algorithm for approximating the radii of point sets, in Proc. APPROX, 2003.

Cited By

David RGoldenberg EKrauthgamer R(2017)Local reconstruction of low-rank matrices and subspacesRandom Structures & Algorithms10.1002/rsa.2072051:4(607-630)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1002/rsa.20720
Guruswami VRaghavendra PSaket RWu Y(2016)Bypassing UGC from Some Optimal Geometric Inapproximability ResultsACM Transactions on Algorithms10.1145/273772912:1(1-25)Online publication date: 8-Feb-2016
https://dl.acm.org/doi/10.1145/2737729
Feldman DTassa TCao LZhang CJoachims TWebb GMargineantu DWilliams G(2015)More Constraints, Smaller CoresetsProceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining10.1145/2783258.2783312(249-258)Online publication date: 10-Aug-2015
https://dl.acm.org/doi/10.1145/2783258.2783312
Show More Cited By

Efficient subspace approximation algorithms
1. Theory of computation

Recommendations

Discriminant Subspace Analysis: A Fukunaga-Koontz Approach

The Fisher Linear Discriminant (FLD) is commonly used in pattern recognition. It finds a linear subspace that maximally separates class patterns according to the Fisher Criterion. Several methods of computing the FLD have been proposed in the literature,...
Efficient Subspace Approximation Algorithms

We consider the problem of fitting a subspace of a specified dimension k to a set P of n points in źd. The fit of a subspace F is measured by the Lź norm, that is, it is defined as the ź-root of the sum of the źth powers of the Euclidean distances of ...
Subspace Approximation of Face Recognition Algorithms: An Empirical Study

We present a theory for constructing linear subspace approximations to face-recognition algorithms and empirically demonstrate that a surprisingly diverse set of face-recognition approaches can be approximated well by using a linear model. A linear ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
264
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

David RGoldenberg EKrauthgamer R(2017)Local reconstruction of low-rank matrices and subspacesRandom Structures & Algorithms10.1002/rsa.2072051:4(607-630)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1002/rsa.20720
Guruswami VRaghavendra PSaket RWu Y(2016)Bypassing UGC from Some Optimal Geometric Inapproximability ResultsACM Transactions on Algorithms10.1145/273772912:1(1-25)Online publication date: 8-Feb-2016
https://dl.acm.org/doi/10.1145/2737729
Feldman DTassa TCao LZhang CJoachims TWebb GMargineantu DWilliams G(2015)More Constraints, Smaller CoresetsProceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining10.1145/2783258.2783312(249-258)Online publication date: 10-Aug-2015
https://dl.acm.org/doi/10.1145/2783258.2783312
Feldman DSchmidt MSohler CKhanna S(2013)Turning big data into tiny dataProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627920(1434-1453)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627920
Varadarajan KXiao X(2012)A near-linear algorithm for projective clustering integer pointsProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095221(1329-1342)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095221
Guruswami VRaghavendra PSaket RWu Y(2012)Bypassing UGC from some optimal geometric inapproximability resultsProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095174(699-717)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095174
Deshpande ATulsiani MVishnoi NRandall D(2011)Algorithms and hardness for subspace approximationProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133075(482-496)Online publication date: 23-Jan-2011
https://dl.acm.org/doi/10.5555/2133036.2133075
Woodruff DFortnow LVadhan S(2011)Near-optimal private approximation protocols via a black box transformationProceedings of the forty-third annual ACM symposium on Theory of computing10.1145/1993636.1993733(735-744)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.1145/1993636.1993733
Feldman DLangberg MFortnow LVadhan S(2011)A unified framework for approximating and clustering dataProceedings of the forty-third annual ACM symposium on Theory of computing10.1145/1993636.1993712(569-578)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.1145/1993636.1993712
Feldman DMonemizadeh MSohler CWoodruff DCharikar M(2010)Coresets and sketches for high dimensional subspace approximation problemsProceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms10.5555/1873601.1873654(630-649)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.5555/1873601.1873654
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten