Questions tagged [high-dimensional]
A high-dimensionality space is one that can only be spanned by a basis set with a large number of elements. High-dimensional problems often suffer from the *Curse of Dimensionality*, which is exponential growth in the problem size as a function of the number of dimensions.
41
questions
0
votes
1
answer
36
views
Dimensionality reduction between discrete wavelet families
I have what it may be a ridiculous question (since I don't know much about wavelets), but here I go.
I am using different Discrete Wavelet families to extract texture features from images. I plan to ...
- 3
0
votes
1
answer
92
views
Planes in n-dimensional space
This is not a homework, but a hobby project, and maybe not all terms I use are correct - please help to fix.
Imagine there are K vectors in n-dimensional space. I would like to:
validate whether they ...
- 193
2
votes
3
answers
188
views
Numerical solution of high-dimensional integral involving positive-part function
Consider a potentially high-dimensional (say, $N$ up to 20) integral of the form
$$
\int_0^\infty \rho_1(x_1)\rho_2(x_2) \cdots \rho_N(x_N) \bigg(x_1+x_2+\cdots+x_N -K\bigg)^+ \, dx_1 \cdots dx_N.
$$
...
- 3,042
2
votes
1
answer
248
views
Efficient projection of a vector onto matrix kernel
Given an $m \times n$ matrix $A$ and a vector $x\in\mathbb R^n$, with $m<n$, what's an efficient way of computing the projection of $x$ onto the kernel of $A$?
- 1,709
0
votes
0
answers
116
views
Solver for large dense BVP system in python
I have a large system of boundary value problems of the form
$$ \frac{d^2 y }{dt^2} = C(t) y + b(t), $$
where the variable $y$ is a vector that has anywhere from 50 to around 500 components, $C$ is a ...
- 1
3
votes
0
answers
126
views
Methods to approximate obective function gradients from point cloud
Problem statement:
Assume that I have an objective function $f(x)$ which takes as input a $D$-dimensional vector $x\in\mathbb{R}^D$, and that $f(x)$ is sufficiently smooth. Assume further that I ...
- 203
3
votes
0
answers
110
views
Numerical solution to N-dimensional diffusion on simplex?
Assume I have a system of at least (but generally only) $N+1$ points in an $N$-dimensional space ($N > 3$ is possible). At each of these points $x_i, i=1,...,N+1$ I know an initial potential/...
- 203
1
vote
1
answer
451
views
Data structure for efficient high dimensional histogramming
What data structure (or C++ library implementing it) is most suitable for efficient high dimensional histogramming?
I have an application where I need to compute something similar to a histogram in a ...
- 11
0
votes
1
answer
215
views
Meshing software: connectivity between elements and boundary
I am implementing an algorithm which produces a 4d mesh for a cylinder with a given 3d base. This means, I have a 3d mesh and I want to generate a 4d mesh for the corresponding space-time cylinder.
...
- 254
0
votes
1
answer
179
views
Solving Poisson equation while suffering from the curse of dimensionality
I have a heat transfer equation in a cube in $R^{100}$: $[0,1]\times[0,1]\times[0,1]\dots$:
$$
\nabla^2 \varphi = f,
$$
with boundary conditions set in a form that in the number of points $p_i$, ...
- 193
0
votes
2
answers
206
views
most efficient way to calculate eigen states of a 2D or 3D potential (Matlab)
I know of several ways to calculated the eigen states of 1D potentials (i.e. DVR, Crank–Nicolson, etc). However I wonder what is the most efficient way to do the same for a N-Dimensional potential? ...
- 101
5
votes
2
answers
338
views
Dimensionality reduction of the domain of f(x)
I'm wondering if there is something analogous to a PCA for data sets where there is a dependent variable. (Though I am interested in any method of dimensionality reduction, PCA is just an example.) ...
- 153
11
votes
3
answers
367
views
What is the current state of the art in solving higher dimensional parabolic PDEs (multi-electron Schrödinger equation)
What is the current state of the art for solving higher dimensional (3-10) parabolic PDEs in the complex domain with simple poles (of the form $ \frac{1}{|\vec{r}_1 - \vec{r}_2|}$) and absorbing ...
- 1,155
4
votes
3
answers
232
views
K-nearest neighbours search in subspaces of a high-dimensional space
I'm looking for a good way to partition a large, fairly high-dimensional dataset in order to perform fast kNN searches not just in the full $N$-dimensional space, but also in lower-dimensional ...
- 237
3
votes
2
answers
451
views
Best incremental multidimensional Delaunay tessellation algorithm
I'm looking for a specific type of Delaunay tessellation algorithm.
The algorithm should be:
incremental so that I can add new sites inside known simplexes (i.e. no searching for the right simplex ...
- 31
3
votes
1
answer
2k
views
Multivariate Orthogonal Polynomial Generation
I'm trying to apply the stochastic galerkin method to partial differential equation with multiple uniform random coefficients. I'm puzzled as to how to extend the corresponding orthogonal (legendre) ...
- 12k
3
votes
1
answer
244
views
Is there an Implementation of the Hilbert curve from $[0,1]$ to $[0,1]^n$, where $n$ is large? ($n=10,000$, say)
I would like to map each point in $[0,1]$ to $[0,1]^n$ with a Hilbert curve, where $n=10,000$. That is
$$
f: [0,1] \to [0,1]^n,
$$
is the $n$-dimensional Hilbert curve.
I found the library of Cortesi,...
user729
11
votes
3
answers
1k
views
N-dimensional Delaunay Tesselation Software Libraries
I have a set of known points/nodes irregularly spaced in N-Dimensional space (N>=2), and I would like a way to generate the Delaunay triangulation of these points, and return the corresponding ...
- 431
4
votes
1
answer
414
views
Multivariate numerical integration with a non-uniform grid
I want to approximate the integral:
$$
I = \int f(\boldsymbol{x})d\boldsymbol{x}
$$
where $\boldsymbol{x}$ is $d$-dimensional. I have a set of non-equally spaced points $\boldsymbol{x}_1, \dots, \...
- 707
1
vote
0
answers
29
views
PCA performed on a configuration with scaled axes
Suppose a configuration $X\in\mathbb{R}^{n\times 2}$ is output of PCA on some high-dimensional data $Y\in\mathbb{R}^{n\times h}$. Note that this PCA is performed by $$X=Y\cdot U,$$ where columns of $U$...
- 1,663
2
votes
1
answer
86
views
Optimality criterion of PCA via recovered distances
It is stated in
http://users.eecs.northwestern.edu/~yingwu/teaching/EECS510/Reading/Williams_NIPS01.pdf
that the PCA mapping from $h$-dimensional data to low $k$-dimensional space minimizes $$\sum_{...
- 1,663
2
votes
1
answer
225
views
$k$-Nearest Neighbor Search using examples
I want to perform $k$-Nearest Neighbor Search in multidimensional space, but not using for example $L_2$-distance. I want the user to specify some "similar"-pairs examples and then perform a search ...
- 213
1
vote
1
answer
122
views
What kinds of maths to learn for understanding dynamical systems in cognitive science? [closed]
A current trend in cognitive science is to view the mind as a dynamical system (e.g., Continuity of Mind by Spivey, in which cognition is understood as a "continuous and often recurrent trajectory ...
5
votes
1
answer
149
views
Configuration shift to change the rank of a Gram matrix
Suppose a matrix $D\in\mathbb{R}^{n\times n}$ of Euclidean distances between $n$ points is given. To obtain a Gram matrix (matrix of inner-products of points that give rise to distances in $D$), one ...
- 1,663
2
votes
1
answer
201
views
Recovering coordinates by eigendecomposition without double-centering
Suppose an Euclidean distance $D\in\mathbb{R}^{n\times n}$ matrix between a set of $n$ objects is given. To obtain inner-products (which will be further be used to recover coordinates), entries of $D$ ...
- 1,663
11
votes
4
answers
14k
views
Fastest PCA algorithm for high-dimensional data
I would like to perform a PCA on a dataset composed of approximately 40 000 samples, each sample displaying about 10 000 features.
Using Matlab princomp function consistently takes over half an hour ...
- 281
3
votes
1
answer
98
views
High-dimensional representation of arbitrary input
Given a symmetric matrix $A\in\mathbb{R}^{n\times n}$ with positive entries and zero diagonal, is it always possible to construct a high-dimensional configuration in Euclidean space, such that these ...
- 1,663
3
votes
2
answers
231
views
How to efficiently compute the total least squares with an inequality constraint
I am looking for an efficient method to compute $$\sum_{i=1}^\left|B\right|\left|Ax_i-b_i\right|^2\rightarrow min$$ under the condition $$\forall i, x_i\ge 0,$$
where $A$ is an n-by-m matrix and $B$ ...
- 133
2
votes
2
answers
183
views
Handling inconsistent solutions obtained by PCA
In order to achieve a 2D representation $X\in\mathbb{R}^{n\times 2}$ of some high-dimensional data residing in $Y\in\mathbb{R}^{n\times k}$, I use PCA:$$X=Y\cdot U,$$where $U\in\mathbb{R}^{k\times 2}$ ...
- 1,663
1
vote
1
answer
94
views
Normalizing axes prior to PCA
For a given centered configuration of points $X\in\mathbb{R}^{n\times 3}$, the covariance matrix is denoted by $S=\frac{1}{n}X^TX$. Recall that the 2D PCA solution is obtained by $Y=X\cdot U$, where $...
- 1,663
0
votes
1
answer
76
views
Relation to all-pairs Euclidean distances
Given $d$-dimensional coordinates residing in a matrix $X\in\mathbb{R}^{n\times d}$, the Euclidean distance between items $i$ and $j$ is denoted as $g_{ij}$. Let $c\in\mathbb{R}^d$ denote the centroid ...
- 1,663
5
votes
1
answer
1k
views
Convex polytope volume and centroid calculation
I have troubles imagining how to compute a volume and centroid of an n-dimesional convex polytope.
For a polygon (especially for convex polygon) the area and centroid are described in (wiki) by
$$
A=...
- 151
2
votes
2
answers
141
views
A sufficient number of distances to recover relative positions of n points
On several places I found different claims on a sufficient number of distances to recover relative positions of $n$ points in $d$-dimensional space.
For instance, work from
http://www.dimitris-...
- 1,663
2
votes
1
answer
100
views
application of oscillatory high-dimensional functions
Has anybody stumbled upon any kind of application of high-frequency high-dimensional problems ($d\geq 4$)?
My interest comes from the following: there is quite a decent amount of papers where people ...
- 21
3
votes
1
answer
363
views
3D to 2D projections, a generalization
Given some data points in 3D, $X\in\mathbb{R}^{n\times 3}$, could one say that
$$Y=XP,$$ for some $P\in\mathbb{R}^{3\times 2}$ actually corresponds to a particular viewpoint on a 3D data? Basically, ...
- 1,663
4
votes
1
answer
146
views
Constructing the origin position by transforming distance information
Suppose a set of $n$ points, $n\in M$, is given in some $d-$dimensional space, $X\in\mathbb{R}^{n\times d}$. Among these $n$ points, some $k\in K$ are selected, so $k<n$, and the distances from ...
- 1,663
2
votes
1
answer
263
views
Proof continuation for rigid transformation on PCA solution
Suppose a matrix $X\in\mathbb{R}^{n\times 3}$ is given as a Principal Component Analysis (PCA) projection from some high dimensional space. The 2D PCA solution on X, say $Y\in\mathbb{R}^{n\times 2}$ ...
- 1,663
5
votes
1
answer
366
views
Working with multi-dimensional functions
How would you represent functions of type $[-1, 1]^n \to \mathbb R \;$ for moderate $n$? How would you integrate them?
For small $n$ (1-2) such functions can be represented as histograms, vectors in ...
- 151
8
votes
2
answers
1k
views
Kolmogorov–Smirnov test for multivariate data
I have a set of files consisting of randomly selected points from a dataset, each file belonging to a particular class. Each row in these files contains the coordinates in n-space of the point. I'd ...
- 181
15
votes
3
answers
792
views
PDEs in Many Dimensions
I know that most methods of finding approximate solutions to PDEs scale poorly with the number of dimensions, and that Monte Carlo is used for situations that call for ~100 dimensions.
What are good ...
- 3,355
5
votes
2
answers
239
views
Enumerating hexahedral cell vertices and faces in arbitrary dimension
I have a Cartesian mesh in $d$ dimensions, and I would like to enumerate all the subcells of a given hexahedral cell. If I am just enumerating the vertices of a cell (or cells that contain a vertex) I ...
- 4,259