We describe a technique to minimize weighted tree automata (WTA), a powerful formalisms
that subsumes probabilistic context-free grammars (PCFGs) and latent-variable PCFGs. Our
method relies on a singular value decomposition of the underlying Hankel matrix defined by
the WTA. Our main theoretical result is an efficient algorithm for computing the SVD of an
infinite Hankel matrix implicitly represented as a WTA. We evaluate our method on real-
world data originating in newswire treebank. We show that the model achieves lower …

Proof. Let n= rank (f). Let B be an arbitrary minimal WTA computing f. Suppose B induces the
rank factorization Hf= PS. Since the columns of both P and P are basis for the column-span
of Hf, there must exists a change of basis Q∈ Rn× n between P and P. That is, Q is an
invertible matrix such that PQ= P. Furthermore, since PS= Hf= PS= P QS and P has full
column rank, we must have S= QS, or equivalently, Q− 1S= S. Thus, we let A= Bq, which
immediately verifies fA= fB= f. It remains to be shown that A induces the rank factorization …