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.
