Is "random projection" strictly speaking not a projection? 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?.
 A: 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.
A: *

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


*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.” 
A: 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
A: If you use recomputable random sign flipping or permutation prior to the Fast Walsh Hadamard transform the random projection is orthogonal.
