Questions tagged [high-dimensional]

Pertains to a large number of features or dimensions (variables) for data. (For a large number of data points, use the tag [large-data]; if the issue is a larger number of variables than data, use the [underdetermined] tag.)

Filter by
Sorted by
Tagged with
236
votes
8answers
71k views

Why is Euclidean distance not a good metric in high dimensions?

I read that 'Euclidean distance is not a good distance in high dimensions'. I guess this statement has something to do with the curse of dimensionality, but what exactly? Besides, what is 'high ...
90
votes
11answers
30k views

Explain “Curse of dimensionality” to a child

I heard many times about curse of dimensionality, but somehow I'm still unable to grasp the idea, it's all foggy. Can anyone explain this in the most intuitive way, as you would explain it to a child,...
54
votes
7answers
26k views

Best PCA algorithm for huge number of features (>10K)?

I previously asked this on StackOverflow, but it seems like it might be more appropriate here, given that it didn't get any answers on SO. It's kind of at the intersection between statistics and ...
36
votes
3answers
57k views

How to estimate shrinkage parameter in Lasso or ridge regression with >50K variables?

I want to use Lasso or ridge regression for a model with more than 50,000 variables. I want do so using software package in R. How can I estimate the shrinkage parameter ($\lambda$)? Edits: Here is ...
22
votes
3answers
2k views

Should dimensionality reduction for visualization be considered a “closed” problem, solved by t-SNE?

I've been reading a lot about $t$-sne algorithm for dimensionality reduction. I'm very impressed with the performance on "classic" datasets, like MNIST, where it achieves a clear separation of the ...
20
votes
1answer
551 views

Why is LASSO not finding my perfect predictor pair at high dimensionality?

I'm running a small experiment with LASSO regression in R to test if it is able to find a perfect predictor pair. The pair is defined like this: f1 + f2 = outcome The outcome here is a predetermined ...
17
votes
1answer
5k views

Should data be centered+scaled before applying t-SNE?

Some of my data's features have large values, while other features have much smaller values. Is it necessary to center+scale data before applying t-SNE to prevent bias towards the larger values? I ...
16
votes
4answers
3k views

Does “curse of dimensionality” really exist in real data?

I understand what is "curse of dimensionality", and I have done some high dimensional optimization problems and know the challenge of the exponential possibilities. However, I doubt if the "curse of ...
15
votes
1answer
570 views

High-dimensional regression: why is $\log p/n$ special?

I am trying to read up on the research in the area of high-dimensional regression; when $p$ is larger than $n$, that is, $p >> n$. It seems like the term $\log p/n$ appears often in terms of ...
13
votes
3answers
7k views

PCA on high-dimensional text data before random forest classification?

Does it make sense to do PCA before carrying out a Random Forest Classification? I'm dealing with high dimensional text data, and I want to do feature reduction to help avoid the curse of ...
12
votes
1answer
4k views

Does Dimensionality curse effect some models more than others?

The places I have been reading about dimensionality curse explain it in conjunction to kNN primarily, and linear models in general. I regularly see top rankers in Kaggle using thousands of features on ...
11
votes
2answers
4k views

Is Multiple Linear Regression in 3 dimensions a plane of best fit or a line of best fit?

Our prof is not getting into the math or even geometric representation of multiple linear regression and this has me slightly confused. On the one hand it's still called multiple linear regression, ...
10
votes
1answer
435 views

Is the relative contrast theorem from Beyer et al. paper: “On the Surprising Behavior of Distance Metrics in High Dimensional Space” misleading?

This is cited very often when mentioning the curse of dimensionality and goes (righthand formula called relative contrast) $$ \lim_{d\rightarrow \infty} \text{var} \left(\frac{||X_d||_k}{E[||X_d||_k]...
9
votes
2answers
6k views

How do I know my k-means clustering algorithm is suffering from the curse of dimensionality?

I believe that the title of this question says it all.
9
votes
7answers
1k views

Find close pairs in very high dimensional space with sparse vectors

I have $N$ (~a million) feature vectors. There are $M$ (~a million) binary features, but in each vector only $K$ (~a thousand) of them would be $1$, the rest are $0$. I'm looking for the pairs of ...
9
votes
3answers
3k views

Curse of dimensionality: kNN classifier

I am reading Kevin Murphy's book: Machine Learning-A probabilistic Perspective. In the first chapter the author is explaining the curse of dimensionality and there is a part which i do not understand. ...
9
votes
3answers
670 views

PCA too slow when both n,p are large: Alternatives?

Problem Setup I have data points (images) of high dimension (4096), which I'm trying to visualize in 2D. To this end, I'm using t-sne in a manner similar to the following example code by Karpathy. ...
9
votes
1answer
186 views

How do children manage to pull their parents together in a PCA projection of a GWAS data set?

Take 20 random points in a 10,000-dimensional space with each coordinate iid from $\mathcal N(0,1)$. Split them into 10 pairs ("couples") and add the average of each pair ("a child") to the dataset. ...
9
votes
2answers
285 views

Uncertainty estimation in high-dimensional inference problems without sampling?

I'm working on a high-dimensional inference problem (around 2000 model parameters) for which we are able to robustly perform MAP estimation by finding the global maximum of the log-posterior using a ...
9
votes
1answer
227 views

High dimensional, correlated data and top features/ covariates discovered; multiple hypothesis testing?

I have a dataset with about 5,000 often correlated features / covariates and a binary response. The data was given to me, I didn't collect it. I use Lasso and gradient boosting to build models. I ...
7
votes
2answers
833 views

How can I quickly detect cheating variables in large data?

Suppose We have a data set with millions rows and thousands columns and the task is binary classification. When we run a logistic regression model, the performance a lot better than expected, e.g, ...
7
votes
1answer
680 views

Where are most points in a uniformly distributed high-dimensional ball?

Should they be close to the middle (origin) or close its surface?
7
votes
3answers
3k views

Curse of dimensionality- does cosine similarity work better and if so, why? [duplicate]

When working with high dimensional data, it is almost useless to compare data points using euclidean distance - this is the curse of dimensionality. However, I have read that using different distance ...
7
votes
2answers
357 views

Generating a high-dimensional dataset where nearest neighbor becomes meaningless

In the paper "When Is 'Nearest Neighbor' Meaningful?" we read that, We show that under certain broad conditions (in terms of data and query distributions, or workload), as dimensionality increases,...
6
votes
2answers
736 views

Explanation for this event on a high-dimensional dataset

Suppose we sample a set $S$ of $n$ points from a $d$-dimensional spherical (unit variance) Gaussian with $d \approx 100$. It is known that any point of the sample would be roughly at $\sqrt{d}$ ...
6
votes
2answers
170 views

Why is Gaussian distribution on high dimensional space like a soap bubble

In this famous post "Gaussian Distributions are Soap Bubbles" it is claimed that the distribution of the points looks like a soap bubble (where it is less dense in the center and more dense at the ...
6
votes
1answer
1k views

Elastic net: dealing with wide data with outliers

Recently I was working on a dataset with ~300 observations and 1500 predictors. I used the glmnet package in R to fit an elastic net model, which gave me a cross-...
6
votes
1answer
279 views

Expected squared distance from origin of training points vs. test points

This is from Exercise 2.4 (Page 39) of Elements of Statistical Learning: The edge effect problem discussed on page 23 is not peculiar to uniform sampling from bounded domains. Consider inputs drawn ...
5
votes
3answers
1k views

Can I use lasso when it is not a high dimensional setting?

I have 500 observations and 200 predictors, and I want to do the prediction while selecting some important features. I know that regularisation method (ridge, lasso) are shrinkage method for high-...
5
votes
2answers
230 views

In what cases is it OK to use categorical predictors with many levels in regression?

If $n\gg p$ ($n$ is the number of observations, $p$ is the number of dimensions), is it always OK to use categorical predictors with many levels in regression? Here $p$ is also pretty high as the ...
5
votes
1answer
685 views

Different definitions of “curse of dimensionality”

I have read two definitions of the curse of dimensionality: The first seems to be more widespread, (I have seen people refer to it on stats.SE in other questions), the other one I only recently ...
5
votes
1answer
97 views

Estimation of Bayesian Models

I'm trying to get into Bayesian model estimation (I'm interested in posterior parameter distributions). I could get away with Metropolis-Hastings and Gibbs Sampling for models with few parameters (<...
5
votes
2answers
189 views

Align noisy point clouds

I have a point cloud $X$ that, I suspect, is a translate of a Gaussian-corrupted version of a subset of a larger cloud $Y$, both high-dimensional ($d$ is at least 100 and ideally 10,000). What is the ...
5
votes
1answer
109 views

Covering the unit sphere with sparse vectors

I'm looking for references for covering the $d$-dimensional unit sphere $$ \mathbb{S}^{d - 1} = \left\{ x \in \mathbb{R}^d : \| x \| = 1 \right\} $$ I'm trying to cover $\mathbb{S}^{d-1}$ with ...
5
votes
0answers
679 views

Why word embeddings learned from word2vec are linearly correlated

I was playing with CBOW from the word2vec program downloaded from https://code.google.com/archive/p/word2vec/ with some sequence data (peptides in this case). I was trying to get embeddings for amino ...
4
votes
1answer
568 views

Things that I am not sure about “LASSO” regression method

I have read the chapters that are related to "LASSO" regression in: The elements of statistical learning (Tibshirani et al.) Statistical Learning with Sparsity: The Lasso and Generalizations. (...
4
votes
1answer
8k views

Clustering high dimensional data (p > n) in R

I have a situation where we have a number of quantitative features / variables (p) than the number of samples (n). My objective is to classify these samples into groups (may be hierarchical). I can ...
4
votes
2answers
5k views

How does linear SVMs function in multi dimensional feature space?

How does linear SVMs function in multi dimensional feature space? I'm not able to picture how a linear SVM can perform classification in more than 2 dimensions. Also, when to chose linear SVMs and ...
4
votes
2answers
2k views

What are the implications of the curse of dimensionality for ordinary least squares linear regression?

My understanding is that the curse of dimensionality implies that we need an exponential amount of data with respect to the number of features we include in our model. Is this correct? If so, what ...
4
votes
1answer
828 views

How to find set of directions in Stahel-Donoho outlyingness measure?

Currently I’m trying to understand and use the Stahel-Donoho outlyngness measure. But unfortunately I’ve got a problem in the part where one is taking the maximum over the set of directions. I found ...
4
votes
3answers
387 views

A Kernel Two Sample Test and Curse of Dimensionality

Gretton et al describes the Kernel Maximum Mean Discrepancy, a measure of distance between distributions. In order to compare two distributions, it turns out you can do much better than, say, taking ...
4
votes
2answers
582 views

Higher-dimensional version of variance

If $X$ is a real-valued random variable, $$\mathbb{E}[X^2] - (\mathbb{E}[X])^2$$ is the variance of $X$. Suppose now that $X$ is a random variable that takes values on $\mathbb{R}^n$. Consider the ...
4
votes
2answers
137 views

Why $p > n$ implies multicollinearity?

Why $p > n$ implies multicollinearity ? $p$ is number of variables, and $n$ is number of samples. I know it has something to do with linear algebra concepts, but I am not sure how do linear algebra ...
4
votes
1answer
632 views

Support Vector Machines and the curse of dimensionality

I am reading this paper: "Automated MR image classification in temporal lobe epilepsy", by Focke et al. NeuroImage, 2012. The authors use support vector machines to classify subjects between healthy ...
4
votes
3answers
5k views

Removing features with low variance in classification models

Almost in every ML models with high dimensional, one of the first things to do is removing features with low variance in order to decrease dimension. But, when we do this, we don't examine the ...
4
votes
1answer
1k views

How does glmnet handle larger datasets?

I'm looking to fit a model with about 1k-40k variables and up to a few million observations. Can anyone with a bit more experience speak to its performance for larger datasets? It looks like I can ...
4
votes
1answer
4k views

What is high dimensional data in data mining?

Currently I am studying effect of high dimensions of data on clustering , for experiment purpose I want to use kdd dataset from UCI which contains 42 features. Is kdd a high dimensional data or what ...
4
votes
2answers
195 views

Linear Filtering in High Dimensional State Space

I am working with Gaussian Linear State Space models of the form: $$y_t=F_t\Theta_t+v_t$$ $$\Theta_t=G_t\Theta_{t-1}+w_t$$ $$v_t \sim N(0, V_t)$$ $$w_t \sim N(0, W_t)$$ Where $y_t$ is my observed ...
4
votes
1answer
467 views

Do linear regression classifiers suffer from the curse of dimensionality?

I am aware that Bayesian models and K-nearest neighbor both suffer in prediction results, especially when the dataset size does not scale exponentially to the number of dimensions. However, does the ...
4
votes
1answer
120 views

Reference for Bayesian statistical methods in high dimensional settings

I am starting to get a knowledge about the Bayesian methods in high dimensional settings. The following two references are what I am getting at. Hjort, Nils Lid. "Bayesian approaches to non-and ...