Let $P$ be a set of $n$ points in $\mathbb{R}^d$ and $Q\subseteq P$ with $\vert Q\vert \geq \alpha n$ for some constant $\alpha\in(0,1]$. Given a $j$-dimensional affine subspace(flat) $F$ consider the follwing objective function

$cost(P,F) =\sum_{p\in P} dist(p,F)^2$, where $dist(p,F) = \min_{q\in F}\Vert p-q\Vert$.

The well-known Low Rank Approximation problem asks to find a j-subspace $F^\star$ such that the cost is (approximately) minimized. This can be done using Sigular Value Decomposition. Moreover, if we want to approximately preserve the cost, then there are weak coreset result that shows that there exists $poly(k/\epsilon)$ points of $P$ such that its span contains a approximately optimal subspace (see for example this).

Now suppose we don't have direct access to $Q$ (as defined above) and we want to find a approximately optimal subspace fitting $Q$. Note that if $j=0$ this can in fact be done. In this case the optimal 0-flat is the centroid of $Q$. In this case, take a uniform random sample of size $poly(1/\epsilon)$ from $P$ and compute the centroid of every $poly(1/\epsilon)$ sized subset of the sample. Then with constant probability one of the centroid is close the actual centroid of $Q$. This can be deduced from Applications of Weighted Voronoi Diagrams and Randomization to Variance-Based k-Clustering, and also appeared in literarure as Superset Sampling.

My question is that "can this be done for $j\geq 1$"? It seems to me that even computing the weak-coresets (as mentioned above) we need to have acces to the entire point set $Q$. More formally does there exists an Algorithm that picks $f(j,\alpha, \epsilon)$ points from $P$ and can compute an approximately optimal flat for $Q$ from these picked points. Here the function $f$ is independent of $n$ and $d$.

Edit: I found some result that states that if one samples $poly(k/\epsilon)$ points then it covers a constant fraction of the points (see Lemma 6 of Low Rank Approximation in the Presence of Outliers).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.