Let's assume I have a tall matrix $\mathbf{X} \in \mathbb{C}^{m\times n}$, where $m \gg n$. I form the Gram matrix $\mathbf{A} = \mathbf{X}^*\mathbf{X}$, where $\mathbf{A} \in \mathbb{C}^{n\times n}$ is Hermitian. As $\mathbf{A}$ is Hermitian, there exists a lower triangular matrix $\mathbf{L} \in \mathbb{C}^{n\times n}$ such that $\mathbf{A} = \mathbf{L}\mathbf{L}^*$ (where $\mathbf{L}$ is the Cholesky factor of $\mathbf{A}$). Is there a way to compute $\mathbf{L}$ without forming $\mathbf{A}$ first?
I saw some things based on Lyapunov equation solvers, but I can't figure how this could help here.
Yes. Run 'thin' QR factorization on $X$ and set $L:=R^*$. This means $R$ is square and $Q$ is tall and skinny, such that $Q^*Q = I_n$. To confirm: $$X=QR\implies X^*X =R^*Q^*QR = R^*R =LL^*$$