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.
 A: 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.
A: 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"))

A: 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:


*

*This a cheesy and totally non-physical model. Sorry!

*Due to floating point imprecision, some of these values will be not-quite-zero instead.

*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).

