|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Testing the Manifold Hypothesis | | Charles Fefferman
; Sanjoy Mitter
; Hariharan Narayanan
; | | Date: |
1 Oct 2013 | | Abstract: | The hypothesis that high dimensional data tend to lie in the vicinity of a
low dimensional manifold is the basis of manifold learning. The goal of this
paper is to develop an algorithm (with accompanying complexity guarantees) for
fitting a manifold to an unknown probability distribution supported in a
separable Hilbert space, only using i.i.d samples from that distribution. More
precisely, our setting is the following. Suppose that data are drawn
independently at random from a probability distribution $PP$ supported on the
unit ball of a separable Hilbert space $H$. Let $G(d, V, au)$ be the set of
submanifolds of the unit ball of $H$ whose volume is at most $V$ and reach
(which is the supremum of all $r$ such that any point at a distance less than
$r$ has a unique nearest point on the manifold) is at least $ au$. Let $L(M,
P)$ denote mean-squared distance of a random point from the probability
distribution $P$ to $M$.
We obtain an algorithm that tests the manifold hypothesis in the following
sense.
The algorithm takes i.i.d random samples from $P$ as input, and determines
which of the following two is true (at least one must be):
egin{enumerate}
item There exists $M in G(d, CV, frac{ au}{C})$ such that $L(M, P) leq C
epsilon.$
item There exists no $M in G(d, V/C, C au)$ such that $L(M, P) leq
frac{epsilon}{C}.$
end{enumerate} The answer is correct with probability at least $1-delta$. | | Source: | arXiv, 1310.0425 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER