Questions tagged [high-dimensional-geometry]
The high-dimensional-geometry tag has no usage guidance.
31 questions
0
votes
0
answers
34
views
An elementary question related to the volume of a spherical object
I'm currently reading this paper and I'm getting hung up on one detail in the following paragraph:
I think the above exponent should be $n-3$ rather than $n-4$. My understanding is that since $f^{-1}(...
- 59
0
votes
0
answers
74
views
kd-tree optimality for orthogonal range search
It is known that a kd-tree can be constructed for $n$ points ($k$-dimensional) in $O(n \log n)$ time and searching of any axis-aligned hyperrectangle can be done in time $O(n^{1-1/k} + out)$ time ...
- 1,187
0
votes
1
answer
78
views
An inequality about median of points in higher dimensions
Let $S$ be a set of points in $\mathbf{R^d}$ and let $m$ be the median of this set of points, i.e. $\sum_{x \in S} || x - y||$ is minimized when we have $y=m$. Now let $z$ be an arbitrary point in $\...
- 1
1
vote
2
answers
191
views
How to find the size of an ϵ-net of a vector space?
Taken from paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke.
Theorem 3. Let $\mathcal{F}$ be a class of functions from $\mathbb{R}^{d} \rightarrow \mathbb{R}$ and ...
- 113
3
votes
0
answers
136
views
Dimentionality Reduction for Lp-Normed Spaces
Are there any dimensionality reduction techniques known for the general $\ell_{p}$-normed spaces for $p \geq 1$?
In the Euclidean space, there is a classical result: Johnson-Lindenstrass lemma that ...
- 1,551
-2
votes
1
answer
199
views
How to calculate complexity in a high dimensional space?
Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong.
For a specific f(), I'm defining a term '...
- 55
-1
votes
1
answer
85
views
Multivariable concave function $(n - 1) f(x) >= \sum_{i=1}^{n} f(x_{-i})$
Define the multi-dimension concave function $f(x): \mathbb{R}^n_+ \rightarrow \mathbb{R}_+$ where $x \in \mathbb{R}^n_+$, here I use $\mathbb{R}_+$ to represent the range $[0, \infty)$ and we let $f(\...
user54970
1
vote
0
answers
110
views
LSH Probabilistic guarantees
A family $H$ is $(r,cr,p_1,p_2)$-sensitive if for all $x,y \in \mathbb{R}^d$ we have:
$\lVert x-y\rVert <r\quad \Rightarrow\quad \Pr[h(x)=h(y)] \geq p_1$, and
$\lVert x-y\rVert > cr \quad \...
- 21
1
vote
1
answer
127
views
Lattice generation inside d-dimensional unit ball
I am interested to know if there is a standard algorithm for generating all the lattice points inside the $d$-dimensional unit ball (with respect to the $\ell_2$-norm).
The brute force approach is to ...
- 11
1
vote
0
answers
77
views
Random Projections and separability
I am new to machine learning and I am considering the following problem:
Suppose you have clusters of points in $\mathbb{R}^N$ with $N$ large. The Johnson-Lindenstrauss lemma specifies how distances ...
- 121
-1
votes
1
answer
170
views
Application of the inequality with expectations
Let $\Vert\cdot\Vert$ is a norm in $R^n$. Let $x_1,\dots,x_N$ non-independent Rademacher random variables random variables (variables which are uniform on $\{-1, 1\}$). . By $E$ we denote an ...
- 141
12
votes
1
answer
645
views
Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?
Imagine we have two size $m$ sets of points $X,Y\subset \mathbb{R}^n$. What is (time) complexity of testing if they differ only by rotation?: there exists rotation matrix $OO^T=O^TO=I$ such that $X=OY$...
- 325
6
votes
0
answers
196
views
An optimal subspace projection problem
Suppose we have a $k$-dimensional subspace $V$ in $\mathbb{R}^n$ given by a basis $\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set $I\subset [n]$ with $|I|=m$ where $k\le m\le n$, such that
$$\...
- 271
2
votes
0
answers
56
views
Lower bound on light spanners in Euclidean space reference
It is well-known that Euclidean space of dimension $d$ has a $(1+\epsilon)$-spanner of weight at most $\epsilon^{-O(d)}\cdot w(MST)$ (see Chapter 14 of Geometric Spanner Network book by Narashimhan ...
- 305
3
votes
1
answer
182
views
Lower bound on probability of getting two close points in a sample of $n$ points
Let $D\subseteq \mathbb{R}^k$. Assume that $Pr_{u,v\leftarrow U_D}[|u-v| <B]>p$ for some $B,p$, where $|u-v|$ is the L1 distance of the vectors.
$S\subseteq D$ is obtained by sampling $n$ ...
- 151
6
votes
1
answer
381
views
Maximum Polyhedron Volume in Given $n$ Points
Suppose we are given $n$ points $v_1,v_2,\cdots, v_n\in \mathbb{R}^k$, I want to find $k+1$ points $v_{i_1}, v_{i_2},\cdots,v_{i_{k+1}}$ such that the volume of the convex body spanned by them ...
- 271
5
votes
0
answers
152
views
Is this volume computation problem #P Hard?
Let $A_{n\times n}$ be a positive definite diagonal matrix with positive rational entries, and let $b$ be a positive rational. Let $R(A,b)$ be the ellipsoid
$ \{\mathbf{x}\in \mathbb{R}^n : ||A\mathbf{...
- 521
1
vote
0
answers
93
views
Do nested convex bodies have increasing "Volume/Surface Area" ratios? [closed]
Suppose we have two convex bodies $A$ and $B$, where $A \subseteq B$. Is it always true that $\mathrm{Vol}(A)/\mathrm{SurfaceArea}(A) \leq \mathrm{Vol}(B)/\mathrm{SurfaceArea}(B)$?
It's true in all ...
- 19
5
votes
0
answers
81
views
Finding of dimension of algebraic varieties
I have found that the problem of finding of dimension of algebraic varieties over $\mathbb{C}$ is $NP$-complete (https://pdfs.semanticscholar.org/a947/463a29ee512b89823176f6e8c9f9b2bb1a5e.pdf).
Are ...
- 2,023
7
votes
3
answers
855
views
Johnson and Lindenstrauss lemma for hamming space
A result of Johnson and Lindenstrauss shows that a set of $n$ points in high
dimensional Euclidean space can be mapped into an $O(\frac{\log n}{\epsilon^2})$- dimensional Euclidean space such that the ...
- 639
2
votes
1
answer
117
views
Data structure for storing points and finding a predecessor of a point
I am looking for a good data structure for storing a set of points
$P\subset \mathbb{N}^n$ that is able to answer the following query:
Given a point $x=(x_1,\cdots,x_n)$, does there exist a point $...
- 123
1
vote
1
answer
68
views
Far point queries in high dimensions
Given a set of points $X\subset R^d$ and a number $r\in R$, create a data structure for queries of the form: "given a point $q\in R^d$ return a point $x\in X$ with $\text{dist}(q,x)\ge r$".
This is ...
- 958
2
votes
0
answers
136
views
Johnson Lindenstrauss for Random variables?
Does the Johnson-Lindenstrauss Lemma apply to any finite-dimensional Hilbert Space? In particular, I am interested in the space of random variables $X = (X_1,...,X_N)$ over $N$ uncertain states. If $\...
- 627
10
votes
1
answer
178
views
Largest cell in an arrangement
Q. What is the complexity of finding the largest volume bounded cell in an arrangment of
$n$ hyperplanes in dimension $d$?
I feel I should know this... But I am not finding a definitive reference.
...
- 3,773
1
vote
1
answer
348
views
Is Locality preserving projections (LPP) method the same as Laplacian eigenmap method?
Are "Locality Preserving projections(LPP)" and "Laplacian eigenmap" one method for dimension reduction, only under different names? I have not seen any article refer to them as the same method, in ...
- 11
10
votes
0
answers
299
views
Approximating a convex polyhedron, with fewer inequalities
I have a convex polyhedron $\mathcal{P}$, given by $n$ linear inequalities $a_i \cdot x \le c_i$ where $x$ is a $d$-dimensional vector over the non-negative real numbers. In other words,
$$\mathcal{...
- 12.4k
4
votes
1
answer
148
views
Batch membership testing for convex polyhedron specified in vertex representation
I have a convex shape defined by a set of vertices (the so-called vertex representation of a convex polyhedron). I also have a large set of points and I would like to test which are contained in the ...
- 3,912
9
votes
1
answer
456
views
VC dimension of Voronoi cells in R^d?
Suppose I have $k$ points in $\mathbb{R}^d$. These induce a Voronoi diagram. If I assign to each of the $k$ points a $\pm$ label, these induce a binary function on $\mathbb{R}^d$. Question: what is ...
- 10.6k
7
votes
1
answer
2k
views
VC dimension of intersection of half-spaces
Define $$l_i(x) := \text{sgn} \left( w_i^\top x - b_i \right)$$
for $i=1,...,n$, where $x \in \mathbb{R}^d$.
Then define the classifier
$$ g(x) := \max \{ l_1(x),..., l_n(x) \}$$
which represents ...
- 205
8
votes
2
answers
223
views
Generating a point in a rational polytope $P \subseteq R^k$ given a point in $P^\epsilon$
Consider a rational polytope $P$ that is defined by means of a separation oracle. That is, $P$ can be described implicitly as $P = \{x \in R^k: Ax \leq b, A \in Z^{m \times k}, b \in Z^m \}$, but ...
- 1,225
9
votes
1
answer
1k
views
Computing volume of high-dimensional convex polyhedra
I am looking for software for computing/estimating volume of high-dimensional convex polyhedra. More specifically, I am interested in a program, which can handle bodies with $n$ vertices in $d$-...
- 1,478