  We study the problem of constructing approximations to a weighted automaton.
Weighted finite automata (WFA) are closely related to the theory of rational
series. A rational series is a function from strings to real numbers that can
be computed by a finite WFA. Among others, this includes probability
distributions generated by hidden Markov models and probabilistic automata. The
relationship between rational series and WFA is analogous to the relationship
between regular languages and ordinary automata. Associated with such rational
series are infinite matrices called Hankel matrices which play a fundamental
role in the theory of minimal WFA. Our contributions are: (1) an effective
procedure for computing the singular value decomposition (SVD) of such infinite
Hankel matrices based on their representation in terms of finite WFA; (2) a new
canonical form for finite WFA based on this SVD decomposition; and, (3) an
algorithm to construct approximate minimizations of a given WFA. The goal of
our approximate minimization algorithm is to start from a minimal WFA and
produce a smaller WFA that is close to the given one in a certain sense. The
desired size of the approximating automaton is given as input. We give bounds
describing how well the approximation emulates the behavior of the original
WFA.
