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.

learn more… | top users | synonyms

4
votes
1answer
74 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.) ...
12
votes
3answers
190 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 ...
4
votes
2answers
121 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 ...
3
votes
1answer
203 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 ...
1
vote
1answer
169 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) ...
3
votes
1answer
147 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 ...
9
votes
3answers
239 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 ...
4
votes
1answer
140 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, ...
1
vote
0answers
24 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 ...
2
votes
1answer
72 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 ...
2
votes
1answer
169 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 ...
1
vote
1answer
83 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 ...
4
votes
1answer
112 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 ...
2
votes
1answer
132 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$ ...
9
votes
4answers
3k 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 ...
3
votes
1answer
81 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 ...
3
votes
2answers
156 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$ ...
2
votes
2answers
94 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
vote
1answer
69 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 ...
0
votes
1answer
57 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 ...
4
votes
1answer
198 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 $$ ...
2
votes
2answers
88 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 ...
2
votes
1answer
85 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 ...
3
votes
1answer
209 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, ...
4
votes
1answer
113 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 ...
2
votes
1answer
184 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}$ ...
4
votes
1answer
192 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 ...
8
votes
2answers
473 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 ...
12
votes
3answers
485 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 ...
5
votes
2answers
196 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 ...