Property Testing of Data Dimensionality

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 t...

Full description

Saved in:
Bibliographic Details
Main Authors: KRAUTHGRAMER, R., SASSON, Ori
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2003
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/1248
http://dl.acm.org/citation.cfm?id=644112
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-2247
record_format dspace
spelling sg-smu-ink.sis_research-22472011-01-04T01:42:00Z Property Testing of Data Dimensionality KRAUTHGRAMER, R. SASSON, Ori 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. 2003-01-01T08:00:00Z text https://ink.library.smu.edu.sg/sis_research/1248 http://dl.acm.org/citation.cfm?id=644112 Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Numerical Analysis and Scientific Computing Software Engineering
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Numerical Analysis and Scientific Computing
Software Engineering
spellingShingle Numerical Analysis and Scientific Computing
Software Engineering
KRAUTHGRAMER, R.
SASSON, Ori
Property Testing of Data Dimensionality
description 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.
format text
author KRAUTHGRAMER, R.
SASSON, Ori
author_facet KRAUTHGRAMER, R.
SASSON, Ori
author_sort KRAUTHGRAMER, R.
title Property Testing of Data Dimensionality
title_short Property Testing of Data Dimensionality
title_full Property Testing of Data Dimensionality
title_fullStr Property Testing of Data Dimensionality
title_full_unstemmed Property Testing of Data Dimensionality
title_sort property testing of data dimensionality
publisher Institutional Knowledge at Singapore Management University
publishDate 2003
url https://ink.library.smu.edu.sg/sis_research/1248
http://dl.acm.org/citation.cfm?id=644112
_version_ 1770570909653925888