Easy way to look at matrix in computational and Hadamard bases?

Question

Given a $2^n \times 2^n$ matrix $M$ of classical data (so, just a bunch of numbers), is there any way to query that matrix in both the computational basis (basically, $M$) and the Hadamard basis, i.e. the matrix $H^{\otimes n}MH^{\otimes n}$ that does not require the explicit matrix multiplication of $H^{\otimes n}MH^{\otimes n}$? Assume that the only structure of $M$ is that it is $k$-sparse, so there is at most $k$ nonzero terms in every row and column, where $k$ is constant.

By "query," I mean we can ask for the nonzero elements and their column indices of any row of the matrix in either basis.

I'm pretty sure the only way would be to explicitly multiply the Hadamard operators with the matrix, but I figured I'd ask just in case.

Answer 1

If you used a Cholesky decomposition of $M = LL^*$, and then kept $L^*$, then when you need an element in the Hadamard basis, you form $L^*H^{\otimes n}$. From this, just take the relevant columns to perform the dot product that produces the element you are querying for.