Property testing of data dimensionality

ABSTRACT

Data dimensionality is a crucial issue in a variety of settings, where it is desirable to determine whether a data set given in a high-dimensional space adheres to a low-dimensional structure. We study this problem in the framework of property testing: Given a query access to a data set S, we wish to determine whether S is low-dimensional, or whether it should be modified significantly in order to have the property. Allowing a constant probability of error, we aim at algorithms whose complexity does not depend on the size of S.We present algorithms for testing the low-dimensionality of a set of vectors and for testing whether a matrix is of low rank. We then address low-dimensionality in metric spaces. For vectors in the metric space l1, we show that low-dimensionality is not testable. For l2, we show that a data set can be tested for having a low-dimensional structure, but that the property of approximately having such a structure is not testable.

REFERENCES

• 1: Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
• 2: {BCL98} H. J. Bandelt, V. Chepoi, and M. Laurent. Embedding into rectilinear spaces. Discrete Comput. Geom., 19(4):595--604, 1998.
• 3: M. Charikar , V. Guruswami , R. Kumar , S. Rajagopalan , A. Sahai, Combinatorial feature selection problems, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.631, November 12-14, 2000
• 4: {DDL+90} S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of the American Society of Information Science, 41(6):391--407, 1990.
• 5: Yevgeniy Dodis , Oded Goldreich , Eric Lehman , Sofya Raskhodnikova , Dana Ron , Alex Samorodnitsky, Improved Testing Algorithms for Monotonicity, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.97-108, August 08-11, 1999
• 6: {DL97} M. Deza and M. Laurent. Geometry of cuts and metrics. Springer-Verlag, Berlin, 1997.
• 7: Tamal K. Dey , Joachim Giesen , Samrat Goswami , Wulue Zhao, Shape dimension and approximation from samples, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.772-780, January 06-08, 2002, San Francisco, California
• 8: Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Journal of Computer and System Sciences, v.60 n.3, p.717-751, June 2000 [doi>10.1006/jcss.1999.1692]
• 9: Uriel Feige, Approximating the bandwidth via volume respecting embeddings, Journal of Computer and System Sciences, v.60 n.3, p.510-539, June 2000 [doi>10.1006/jcss.1999.1682]
• 10: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
• 11: {Fis01} E. Fischer. The art of uninformed decisions: A primer to property testing. Bulletin of the European Association for Theoretical Computer Science. EATCS, (75):97--126, 2001.
• 12: Eldar Fischer , Ilan Newman, Testing of matrix properties, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.286-295, July 2001, Hersonissos, Greece [doi>10.1145/380752.380812]
• 13: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 14: {HH78} F. Hadlock and F. Hoffman. Manhattan trees. Utilitas Math., 13:55--67, 1978.
• 15: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 16: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 17: {JL84} W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), pages 189--206. Amer. Math. Soc., Providence, RI, 1984.
• 18: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 19: {Men28} K. Menger. Untersuchungen uber allgemeine metrik. Mathematische Annalen, 100:75--163, 1928.
• 20: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 21: Vitali D Milman , Gideon Schechtman, Asymptotic theory of finite dimensional normed spaces, Springer-Verlag New York, Inc., New York, NY, 1986
• 22: {Oxl92} J. G. Oxley. Matroid theory. Oxford Science Publications. The Clarendon Press Oxford University Press, New York, 1992.
• 23: Michal Parnas , Dana Ron, Testing metric properties, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.276-285, July 2001, Hersonissos, Greece [doi>10.1145/380752.380811]
• 24: {Ron01} D. Ron. Property testing. In P. Pardalos, S. Rajasekaran, J. Reif, and J. Rolim, editors, Handbook of Randomized Computing. Kluwer Academic, 2001.
• 25: {RR98} Y. Rabinovich and R. Raz. Lower bounds on the distortion of embedding finite metric spaces in graphs. Discrete Comput. Geom., 19(1):79--94, 1998.
• 26: Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

Additional Classification:
  G. Mathematics of Computing
  G.m MISCELLANEOUS

General Terms:
Algorithms, Theory