9
$\begingroup$

Current implementations of the Random Projection algorithm reduce the dimensionality of data samples by mapping them from $\mathbb R^d$ to $\mathbb R^k$ using a $d\times k$ projection matrix $R$ whose entries are i.i.d. from a suitable distribution (for instance from $\mathcal N(0,1)$):

$x^\prime = \frac{1}{\sqrt k}xR$

Conveniently, theoretical proofs exist showing that this mapping approximately preserves pairwise distances.

However, recently I found these notes where the author claims that this mapping with a random matrix is not a projection in the strict linear algebraic sense of the word (page 6). From the explanations given there, this is because the columns of $R$ are not strictly orthogonal when its entries are independently chosen from $\mathcal N(0,1)$. Therefore, earlier versions of RP where the orthogonality of the columns of $R$ was enforced can be considered as a projection.

Can you provide a more detailed explanation of (1) what is the definition of a projection in this strict sense and (2) why isn't RP a projection under this definiton?.

$\endgroup$
1
  • 1
    $\begingroup$ You can find answers to (1) by searching our site. The assertion (2) is immediate because if the columns were always orthogonal, their entries could not be independent. $\endgroup$
    – whuber
    Dec 14 '18 at 14:59
4
+100
$\begingroup$
  1. What is the definition of a projection in this strict (linear algebraic) sense (of the word)

    https://en.wikipedia.org/wiki/Projection_(linear_algebra)

    In linear algebra and functional analysis, a projection is a linear transformation $P$ from a vector space to itself such that $P^2 = P$. That is, whenever $P$ is applied twice to any value, it gives the same result as if it were applied once (idempotent).

    For orthogonal projection or vector projection you have that

    https://en.wikipedia.org/wiki/Projection_(linear_algebra)

    An orthogonal projection is a projection for which the range U and the null space V are orthogonal subspaces.

  2. Why isn't RP a projection under this definition?

    Michael Mahoney writes in your lecture notes that it depends on how the RP is constructed, whether or not the RP is a projection in the traditional linear algebraic sense. This he does in the third and fourth points:

    Third, if the random vectors were exactly orthogonal (as they actually were in the original JL constructions), then we would have that the JL projection was an orthogonal projection

    ...

    but although this is false for Gaussians, $\lbrace \pm \rbrace $ random variables, and most other constructions, one can prove that the resulting vectors are approximately unit length and approximately orthogonal

    ...

    this is “good enough.”

    So you could do, in principal, the random projection with a different construction that is limited to orthogonal matrices (although it is not needed). See for instance the original work:

    Johnson, William B., and Joram Lindenstrauss. "Extensions of Lipschitz mappings into a Hilbert space." Contemporary mathematics 26.189-206 (1984): 1.

    ...if one chooses at random a rank $k$ orthogonal projection on $l_2^n$

    ...

    To make this precise, we let $Q$ be the projection onto the first $k$ coordinates of $l_2^n$ and let $\sigma$ be normalized Haar measure on $O(n)$, the orthogonal group on $l_2^n$. Then the random variable $$f: (O(n), \sigma) \to L(l_2^n)$$ defined by $$f(u) = U^\star Q U$$ determines the notion of a "random rank $k$ projection."

    The wikipedia entry describes random projection in this way (the same is mentioned in the lecture notes on pages 10 and 11)

    https://en.wikipedia.org/wiki/Random_projection#Gaussian_random_projection

    The first row is a random unit vector uniformly chosen from $S^{d − 1}$. The second row is a random unit vector from the space orthogonal to the first row, the third row is a random unit vector from the space orthogonal to the first two rows, and so on.

    But you do not generally get this orthogonality when you take all the matrix-entries in the matrix random and independent variables with a normal distribution (as Whuber mentioned in his comment with a very simple consequence "if the columns were always orthogonal, their entries could not be independent").

    The matrix $R$ and the product in the case of orthonormal columns, can be seen as a projection because it relates to a projection matrix $P = R^TR$. This is a bit the same as seeing ordinary least squares regression as a projection. The product $b = R^T x$ is not the projection but it gives you a coordinate in a different basis vector. The 'real' projection is $x' = Rb = R^TRx$, and the projection matrix is $R^TR$.

    The projection matrix $P=R^TR$ needs to be the identity operator on the subspace $U$ that is the range of the projection (see the properties mentioned on the wikipedia page). Or differently said it needs to have eigenvalues 1 and 0, such that the subspace for which it is the identity matrix is the span of the eigenvectors associated to the eigenvalues 1. With random matrix-entries you are not going to get this property. This is the second point in the lecture notes

    ... it “looks like” an orthogonal matrix in many ways ... the $range(P^T P)$ is a uniformly distributed subspace ... but the eigenvalues are not in $\lbrace 0, 1 \rbrace$.

    note that in this quote the matrix $P$ relates to the matrix $R$ in the question and not to the projection matrix $P = R^TR$ that is implied by the matrix $R$

    So random projection by different constructions, such as using random entries in the matrix, is not exactly equal to an orthogonal projection. But it is computationally simpler and, according to Michael Mahoney, it is “good enough.”

$\endgroup$
2
  • 1
    $\begingroup$ Thanks for your answer, I think it goes in the same direction as the one I gave above. Just to clarify I think you should indicate that $P = RR^T$. Then as you explain, if the entries of $R\in\mathbb R^{d\times k}$ are i.i.d. from $\mathcal N(0,1)$ we cannot ensure that $P^2 = P$ or that $P$ has eigenvalues in $\{0,1\}$. Conversely, if the columns of $R$ are orthonormal both conditions are fulfilled. But it is key to indicate that the projection is $RR^T$, and not $R$ alone! $\endgroup$ Dec 17 '18 at 18:04
  • 1
    $\begingroup$ @DanielLópez I have updated it. $\endgroup$ Dec 18 '18 at 8:34
7
$\begingroup$

That is right: "random projection" is strictly speaking not a projection.

Projection a is clearly defined mathematical object: https://en.wikipedia.org/wiki/Projection_(linear_algebra) -- it is a linear idempotentent operator, i.e. linear operator $P$ such that $P^2 = P$. Applying a projection twice is the same as applying it only once because after a point is projected on a subspace, it should just stay there if projected again. There is nothing about orthogonality in this definition; in fact, a projection can be oblique (see Wikipedia).

Note that only square matrices can represent "projections" in this sense. "Random projection" uses a random $d\times k$ matrix $R$ with $k\ll d$, so it cannot possibly be a projection in the sense of the above definition.

Even if you make the columns of $R$ orthonormal (e.g. by applying Gram-Schmidt process), this argument will still apply. Somebody has recently asked this question about PCA: What exactly should be called "projection matrix" in the context of PCA? -- a $d\times k$ matrix $U$ of orthonormal eigenvectors is strictly speaking not a projection either.

$\endgroup$
12
  • 3
    $\begingroup$ In your last paragraph you say that if the columns are orthonormal then the projection is still not a projection in the sense of a projection in linear algebra. However, this is just because the matrix is not a square matrix. This is more due to notation than due to principle. If you extend the matrix with zero's then the matrix is a linear projection. $\endgroup$ Dec 17 '18 at 15:34
  • 1
    $\begingroup$ @MartijnWeterings No, I don't think so. Take 2D space and U that is 1x2 and looks like this: [sqrt(2)/2, sqrt(2)/2] (corresponding to the projection on the diagonal). Now extend it with zeros. It won't be equal to itself squared. $\endgroup$
    – amoeba
    Dec 17 '18 at 16:21
  • 1
    $\begingroup$ It should be extended some other way, can be done $\endgroup$ Dec 17 '18 at 16:28
  • 2
    $\begingroup$ @amoeba, I agree that it is stretching the concept/definition, but I would say that it is more nuanced than $R (R^TR)^{-1}R^T$ which includes this inverse term that is not equal to $I$. The linear combination $U$ when made out of orthogonal vectors does resemble an orthogonal projection onto a smaller subspace and you can repeat that projection resulting in the same. It is only that along with the projection a different set of basis vectors is chosen (at least that is how one can see it) and the matrix representation is not working like $P^2=P$, but geometrically it looks like a projection. $\endgroup$ Dec 17 '18 at 21:16
  • 2
    $\begingroup$ That's right, @MartijnWeterings, but why would any $R$ with non-orthogonal columns not "look like" an oblique projection? $\endgroup$
    – amoeba
    Dec 17 '18 at 22:53
1
$\begingroup$

I think the key here is to consider the column space of the $d\times k$ RP matrix $R$ as the subspace onto which we perform the projection. In general, regardless of whether the columns of $R$ are orthogonal, one can project a sample $x\in \mathbb R^d$ onto the column space of $R$ ussing the following equation [1]:

$p = xR(R^TR)^{-1}R^T$, where $p\in\mathbb R^d$.

If as in the older versions or RP the columns of matrix $R$ are restricted to be orthonormal, then $R^TR = I\in \mathbb R^{k\times k}$, and therefore the projection of $x$ onto the column space of $R$ becomes:

$p = xRR^T$, with $p\in\mathbb R^d$,

and $RR^T\in\mathbb R^{d\times d}$ becomes a projection matrix, because it's square and $(RR^T)^2=RR^TRR^T=RR^T$.

Perhaps the claim that the older version of Random Projection (were the columns of $R$ were orthonormal) is in fact a projection refers to the fact that in that case the embedding down to $\mathbb R^k$ and posterior reconstruction back to $\mathbb R^d$ of a sample $x\in\mathbb R^d$ given by $xRR^T$ is indeed a projection onto the column space of $R$, and $RR^T$ is a projection matrix.

I would be grateful if you could confirm/correct my reasoning here.

Reference:

[1] http://www.dankalman.net/AUhome/classes/classesS17/linalg/projections.pdf

$\endgroup$
3
  • 1
    $\begingroup$ That's correct but for any R, the matrix $R(R^T R)^{-1} R^T$ that you use in the first formula is a projection too. So I don't think that orthogonality of the R columns matters for the argument that you give in the last paragraph. $\endgroup$
    – amoeba
    Dec 17 '18 at 16:25
  • 1
    $\begingroup$ True, but my point was that maybe you want $RR^T$ to be the projection matrix, as it matches the natural embed and reconstruct logic in dimensionality reduction. Also, that way the columns of $R$ form an orthonormal basis of the subspace (column space of R). I will contact the author of the notes to see if they can shed some light on this. Thanks for your answer! $\endgroup$ Dec 17 '18 at 16:33
  • 2
    $\begingroup$ @amoeba the matrix $R(R^TR)^{-1}R^T$ is indeed a projection as well, but the random projection is not using the $(R^TR)^{-1}R^T$ part, but instead $R^T$. When you have orthonormal columns then this pseudo inverse part equals the matrix $R^T$. You could see it similar to regarding OLS, computing $\beta=(R^TR)^{-1}R^Ty$, as a projection, but the coefficients $\beta$ are not the projection. OLS is strictly only a projection when you compute $\hat{y}=R(R^TR)^{-1}R^Ty$. Still $\beta$ could be considered the projection in a different basis. It is more like a semantic thing than mathematical. $\endgroup$ Dec 18 '18 at 9:04
-1
$\begingroup$

If you use recomputable random sign flipping or permutation prior to the Fast Walsh Hadamard transform the random projection is orthogonal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.