Questions tagged [high-dimensional-geometry]
The high-dimensional-geometry tag has no usage guidance.
8
questions with no upvoted or accepted answers
9
votes
0answers
258 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{...
6
votes
0answers
142 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
$$\...
5
votes
0answers
145 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{...
5
votes
0answers
72 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
votes
0answers
38 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 ...
2
votes
0answers
120 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 $\...
1
vote
0answers
78 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 \...
1
vote
0answers
63 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 ...
