Efficient Identification of Butterfly Sparse Matrix Factorizations
  Fast transforms correspond to factorizations of the form $\mathbf{Z} =
\mathbf{X}^{(J)} \ldots \mathbf{X}^{(1)}$, where each factor
$\mathbf{X}^{(\ell)}$ is sparse and possibly structured. This paper
investigates essential uniqueness of such factorizations, i.e. uniqueness up to
unavoidable scaling ambiguities. Our main contribution is to prove that any $N
\times N$ matrix having the so-called butterfly structure admits an essentially
unique factorization into $J$ butterfly factors (where $N = 2^J$), and that the
factors can be recovered by a hierarchical factorization method, which consists
in recursively factorizing the considered matrix into two factors. This
contrasts with existing approaches which fit the product of butterfly factors
to a given matrix via gradient descent. The proposed method can be applied in
particular to retrieve the factorizations of the Hadamard or the discrete
Fourier transform matrices of size $N=2^J$. Computing such factorizations costs
$\mathcal{O}(N^{2})$, which is of the order of dense matrix-vector
multiplication, while the obtained factorizations enable fast $\mathcal{O}(N
\log N)$ matrix-vector multiplications. This hierarchical identifiability
property relies on a simple identifiability condition in the two-layer and
fixed-support setting.
