Paper Info
Title
Testing Proximity to Subspaces: Approximate $$ell _infty $$ ℓ ∞ Minimization in Constant Time
Abstract
We consider the subspace proximity problem: Given a vector $${\varvec{x}} \in {\mathbb {R}}^n$$ and a basis matrix $$V \in {\mathbb {R}}^{n \times m}$$, the objective is to determine whether $${\varvec{x}}$$ is close to the subspace spanned by V. Although the problem is solvable by linear programming, it is time consuming especially when n is large. In this paper, we propose a quick tester that solves the problem correctly with high probability. Our tester runs in time independent of n and can be used as a sieve before computing the exact distance between $${\varvec{x}}$$ and the subspace. The number of coordinates of $${\varvec{x}}$$ queried by our tester is $$O(\frac{m}{\epsilon }\log \frac{m}{\epsilon })$$, where $$\epsilon $$ is an error parameter, and we show almost matching lower bounds. By experiments, we demonstrate the scalability and applicability of our tester using synthetic and real data sets.
Year
DOI
Venue
2020
10.1007/s00453-019-00642-0
Algorithmica
Keywords
DocType
Volume
Constant-time algorithm, Property testing, Subspace proximity problem, VC dimension
Journal
82
Issue
ISSN
Citations 
5
0178-4617
0
PageRank 
References 
Authors
0.34
11
2
Name
Order
Citations
PageRank
Hayashi, Kohei115915.31
Yuichi Yoshida246944.88