# Fast approximate construction of orthogonal system

Assuming I have $d+1\in\mathbb{R}^d$ points that are not unfortunately chosen (in which case I can just resample, correct me if I $d$ points are enough), then these should span the whole space.

What I'm really interested in is the orientation of the space. These points define a particular rotation.

I can compute the covariance matrix and to PCA. The eigenvalue matrix is a good description of the generated orientation. However, this requires $O(d^3)$ operations to compute. Is there any good method to produce a similar, eventually just approximate, result is less time? I just need reasonable good candidates, then I can validate them and compute "proper" PCA only on the best candidate; but I need to compute these candidates much faster than $O(d^3)$.

The main goal is to estimate hyperplanes the data may lie on to detect multi-variate correlations. With PCA I would obtain both the orientation and the standard deviations, but it is too expensive for high dimensionality.

-
What do you mean by "the orientation of the space"? How do the points define a rotation? –  Rahul Jun 13 '12 at 18:46
You can compute a covariance matrix and decompose this into a rotation and a scaling matrix. See PCA for details. –  Anony-Mousse Jun 13 '12 at 20:51
So, to be clear, you have $d+1$ points $x_i \in \mathbb R^d$, and you want to approximate the eigenvectors of the covariance matrix $\frac1{d+1}\sum (x_i - \bar x) (x_i - \bar x)^T$? –  Rahul Jun 13 '12 at 21:36
I'm fine with any other similar method, too, that gives me "direction" vectors and associated variances (which should be computable in O(n^2) anyway). I need reasonable candidates, but faster than the common exact methods for matrix inversion or eigenvector decomposition which all are O(n^3). –  Anony-Mousse Jun 13 '12 at 21:44