# Does dimension reduction always lose some information?

Like the title says, does dimension reduction always lose some information? Consider for example PCA. If the data I have is very sparse, I would assume a "better encoding" could be found (is this somehow related to the rank of the data?), and nothing would be lost.

• No, of course not: some of the singular values in PCA can be true zeros, for instance. This is less related to the "sparseness" of the data than it is to whether they "fill out" the dimensions used to record them. – whuber Jul 30 '13 at 21:20
• Ok, I see. Could you write your comment as a short answer (maybe even with a small example, if you have time)? – wondering Jul 30 '13 at 21:43
• Consider the case where you have two dimensional data, where the y-value for each point is '0'. Your first principle component will be the X axis, and you won't lose anything by projecting your data down into this single dimension because it's effectively one dimensional already. – David Marx Jul 31 '13 at 3:47

Dimensionality reduction does not always lose information. In some cases, it is possible to re-represent the data in lower-dimensional spaces without discarding any information.

Suppose you have some data where each measured value is associated with two ordered covariates. For example, suppose you measured signal quality $Q$ (indicated by color white=good, black=bad) on a dense grid of $x$ and $y$ positions relative to some emitter. In that case, your data might look something like the left-hand plot [*1]:

It is, at least superficially, a two dimensional piece of data: $Q(x,y)$. However, we might know a priori (based on the underlying physics) or assume that the it depends only on the distance from the origin: r = $\sqrt{x^2 + y^2}$. (Some exploratory analysis might also lead you to this conclusion if even the underlying phenomenon isn't well understood). We could then rewrite our data as $Q(r)$ instead of $Q(x,y)$, which would effectively reduce the dimensionality down to a single dimension. Obviously, this is only lossless if the data is radially symmetric, but this is a reasonable assumption for many physical phenomena.

This transform $Q(x,y) \rightarrow Q(r)$ is non-linear (there's a square root and two squares!), so it is somewhat different from the sort of dimensionality reduction performed by PCA, but I think it's a nice example of how you can sometimes remove a dimension without losing any information.

For another example, suppose you perform a singular value decomposition on some data (SVD is a close cousin to--and the often the underlying guts of--principal components analysis). SVD takes your data matrix $M$ and factors it into three matrices such that $M = USV^{T}$. The columns of U and V are the left and right singular vectors, respectively, which form a set of orthonormal bases for $M$. The diagonal elements of $S$ (i.e., $S_{i,i})$ are singular values, which are effectively weights on the $i$th basis set formed by the corresponding columns of $U$ and $V$ (the rest of $S$ is zeros). By itself, this doesn't give you any dimensionality reduction (in fact, there are now 3 $NxN$ matrices instead of the single $NxN$ matrix you started with). However, sometimes some diagonal elements of $S$ are zero. This means that the corresponding bases in $U$ and $V$ aren't needed to reconstruct $M$, and so they can be dropped. For example, suppose the $Q(x,y)$ matrix above contains 10,000 elements (i.e., it's 100x100). When we perform an SVD on it, we find that only one pair of singular vectors has a non-zero value [*2], so we can re-represent the original matrix as the product of two 100 element vectors (200 coefficients, but you can actually do a bit better [*3]).

For some applications, we know (or at least assume) that the useful information is captured by principal components with high singular values (SVD) or loadings (PCA). In these cases, we might discard the singular vectors/bases/principal components with smaller loadings even if they are non-zero, on the theory that these contain annoying noise rather than a useful signal. I've occasionally seen people reject specific components based on their shape (e.g., it resembles a known source of additive noise) regardless of the loading. I am not sure if you would consider this a loss of information or not.

There are some neat results about the information-theoretic optimality of PCA. If your signal is Gaussian and corrupted with additive Gaussian noise, then PCA can maximize the mutual information between the signal and its dimensionality-reduced version (assuming the noise has a identity-like covariance structure).

Footnotes:

1. This a cheesy and totally non-physical model. Sorry!
2. Due to floating point imprecision, some of these values will be not-quite-zero instead.
3. On further inspection, in this particular case, the two singular vectors are the same AND symmetric about their center, so we could actually represent the entire matrix with only 50 coefficients. Note that the first step falls out of the SVD process automatically; the second requires some inspection/a leap of faith. (If you want to think about this in terms of PCA scores, the score matrix is just $US$ from the original SVD decomposition; similar arguments about zeros not contributing at all apply).
• I don't think your graph is right. 1) It's an ellipse not a circle, so $I(r)$ will change based on the angle with the axes. But this may be an artifact. 2) A PCA where some of the eigenvalues are 0 indicates collinearity in the data; this would be a plot that's a straight line, not a spherical bump. 3) In real life, data is never perfectly symmetrical anyway. – Hong Ooi Jul 31 '13 at 3:00
• In particular, note that $r = \sqrt{(x^2 + y^2)}$ in your example. This is a nonlinear combination of the variables, so it isn't relevant when talking about PCA (which would detect linear combinations in the data). – Hong Ooi Jul 31 '13 at 4:50
• Matt, my question really amounted to this: you show us a picture without any description or reference and refer to it as "data": I would like to know in what sense you are thinking of it as data. Your comment confuses this issue, because a "heat map" representation is usually not data, but is something created out of data. If those were irregular 2D point data, for instance, and you fit a radially symmetric density to them, then the picture could be construed as one-dimensional, as you argue, but it would not be a lossless dimensionality reduction of the data. – whuber Jul 31 '13 at 15:43
• Perhaps I should have said 'gridded' or 'raster' instead. I was imagining a situation where data are collected on a grid and each grid points is associated with a (scalar) value, but the values are not necessarily light intensity as in a (photographic) image. That said, I am clearly not rocking this answer--let me try editing it into something more coherent! – Matt Krause Jul 31 '13 at 16:56
• +1: the edits make your points much clearer. Thanks for the extra effort! – whuber Jul 31 '13 at 18:54

I think the question behind your question is "what makes information?". It is a good question.

Grammar technicality:

Does PCA always lose information? Nope. Does it sometimes lose information? Youbetcha. You can reconstruct the original data from components. If it always lost information then this would not be possible.

It is useful because it often does not lose important information when you use it to reduce dimension of your data. When you lose data it is often the higher frequency data and often that is less important. The large-scale, general trends, are captured in the components associated with the larger eigenvalues.

No. If one or more of the dimensions of an $n \times p$ matrix are a function of the other dimensions, the appropriate dimension reduction technique will not lose any information.

In the most straightforward case, if one dimension is a linear combination of the others, reducing the dimensionality by one can be done without losing any information - because the dropped dimension could be re-created if necessary from what is left.

Consider this three dimensional case where x3 is an exact linear combination of x1 and x2. It's not obvious from eyeballing the original data, although it's clear x3 is related to both the other two:

But if we look at the principal components, the third is zero (within numerical error).

The plot of the first two principal components is the same as the plot of x1 against x2, just rotated (ok, not as obvious I meant, I'll try to explain better later):

We've reduced the dimensionality by one yet kept all the information, by any reasonable definition.

This extends beyond linear dimension-reduction too, although naturally gets more complex to illustrate. The point is that the overall answer is "no", not when some of the dimensions are functions of a combination of the others.

R code:

library(GGally)

n <- 10^3
dat <- data.frame(x1=runif(n, 0, 3), x2=rnorm(n))
dat$x3 <- with(dat, x1 + x2) ggpairs(dat) pc <- princomp(dat) plot(pc) par(mfrow=c(1,2)) with(dat, plot(dat$x1, dat\$x2, col="red", main="Original data", bty="l"))
with(pc, plot(scores[,1], scores[,2], col="blue", main="Scores from principal components(\n(rotated)", bty="l"))