Suppose I have an $?? \times n$ matrix $A$ that is only accessible through matrix-vector products $Ax$. These are expensive in my application, is there a way to approximate vector $x$ of $n$ column norms of $A$ by using less than $n$ calls to the matrix-vector product?
Exact calculation using $n$ calls for $n=3$
$$ \begin{aligned}a_{1}=A \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}\\a_{2}=A\begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}\\a_{3}=A\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}\\\\ x=\langle\left\| a_{1}\right\|,\left\| a_{2}\right\|,\left\| a_{3}\right\| \rangle\end{aligned} $$