# Generating pseudo-random orthonormal bases for random projection

I am performing series of random projections i.e. projecting the input matrix onto randomly generated orthonormal bases (of much lower dimensionality). The projection is just a matrix multiplication like $A \cdot B = P$, where $B$ is the basis composed of several mutually orthogonal column vectors of unit length.

I have come to conclusion that there is no need to generate new basis before each projection because simple permutation of its rows should be sufficient to keep the randomness of the whole process. If this is true, doing so would be very profitable in terms of computational complexity, since row-permutation also keeps orthonormality of the basis.

The problem is that I am a programmer and no matematician, so I'm not sure if indeed projections over such bases are random and thus independent of each other, or they are somehow similar and thus limited. Is my idea right or wrong, and why?

Edited:

The matrix $A$ consists of $n$ row vectors of binary values ($0$ or $1$), where the vector dimension is close to $n$ which is between $10^5$ and $10^7$.

The process of repeating random projections aims to find well-clusterable projection, or at least avoid worst cases. Currently the clusterability is defined as variance.

In order to minimize complexity of row permutation I'm just rotating row indices, so the original basis is not altered at all.

The final goal is to reduce dimensionality of the input vectors and then cluster them in this low-dimensional space with some distance or density based algorithm.

$$B = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \\ \end{pmatrix}$$

The above counterexample clearly shows potential risk of generating a basis which is insensitive to certain permutation - exchange rows 1 and 2, and the result is the same as changing the order of basis vectors, which does not change the projection at all.

Question 1: What is the probability of generating a random basis with such an inherent flaw.

I see that row permutation somehow reflects the basis, but I don't know which bases do not reflect well. I do not expect exact numbers, since it would require precise definition of words "have", "flaw" and "well". Any help in expressing the problem more profesionally is greatly welcome.

Question 2: Is it the only sort of flaw that can reduce randomness of the entire process?

• Welcome to SciComp.SE, Adam! At the moment it's a bit hard to answer your question since we don't know what you are trying to achieve by your random projections, so you should add a bit of background to your question. – Christian Clason Jul 10 '13 at 15:16
• (On the face of it, your last question has the simple answer "It's wrong, since the order of basis vectors is irrelevant with regard to the space they generate", but I'm sure there's a more interesting question behind this.) – Christian Clason Jul 10 '13 at 15:19
• @christian Thank you for your interest. In response to your first comment: I'm repeating the projections (dimensionality reduction) to limit the risk of "bad" projection, because I need a well "clusterable" projection (currently my clusterability measure is just variance). Regarding the second comment: The basis vectors are column vectors, and I permute their rows, so it's not the order of basis vectors that changes, but the vectors' elements. In fact, to simplify the permutation, I just rotate the row indices, so it's all done in-place. – Adam Jul 10 '13 at 15:40
• Sorry, I didn't read carefully enough. Still, a permutation is not sufficient -- it's easy to construct counterexamples (take $(1,0,0)$ and $(0,1,0)$ and permute the first two indices). You really should describe in much more detail what is your goal is here (what does $A$ represent? how do you define a "bad" projection?) by editing the question. – Christian Clason Jul 10 '13 at 15:49
• Also, you should mention that you have already this question on Mathematics.SE; cross-posting is frowned upon (the correct procedure is to wait a few days, and then request migration). – Christian Clason Jul 10 '13 at 15:50