Given a positive-definite $n\times n$ matrix $\mathbf{A}$, my goal is to present it as a product of the form $\mathbf{H^TH}$, where $\mathbf{H}$ is an arbitrary $n\times n$ matrix.
Cholesky decomposition does this with $\mathbf{H}$ upper-triangular. However, its complexity is of the order $O(n^3)$. The question is whether it is possible to do this quicker if we remove all the constraints on $\mathbf{H}$.