Optimal Spectral-Norm Approximate Minimization of Weighted Finite Automata

We denote with $\mathbb{N}$, $\mathbb{Z}$ and $\mathbb{R}$ the set of natural, integers and real numbers, respectively. We use bold letters for vectors and matrices; all vectors considered are column vectors. We denote with $\mathbf{1}$ the identity matrix, specifying its dimension only when not clear from the context. We refer to the $i$-th row and the $j$-th column of $\mathbf{M}$ by $\mathbf{M}(i,:)$ and $\mathbf{M}(:,j)$. Given a matrix $\mathbf{M}\in\mathbb{R}^{p\times q}$ of rank $n$, a rank factorization is a factorization $\mathbf{M}=\mathbf{P}\mathbf{Q}$, where $\mathbf{P}\in\mathbb{R}^{p\times n}$, $\mathbf{Q}\in\mathbb{R}^{n\times q}$ and $\operatorname{rank}(\mathbf{P})=\operatorname{rank}(\mathbf{Q})=n$. Let $\mathbf{M}\in\mathbb{R}^{p\times q}$ of rank $n$, the compact singular value decomposition SVD of $\mathbf{M}$ is the factorization $\mathbf{M}=\mathbf{U}\mathbf{D}\mathbf{V}^{\top}$, where $\mathbf{U}\in\mathbb{R}^{p\times n}$, $\mathbf{D}\in\mathbb{R}^{n\times n}$, $\mathbf{V}\in\mathbb{R}^{q\times n}$ are such that $\mathbf{U}^{\top}\mathbf{U}=\mathbf{V}^{\top}\mathbf{V}=\mathbf{1}$, and $\mathbf{D}$ is a diagonal matrix. The columns of $\mathbf{U}$ and $\mathbf{V}$ are called left and right singular vectors, while the entries of $\mathbf{D}$ are the singular values. The Moore-Penrose pseudo-inverse $\mathbf{M}^{+}$ of $\mathbf{M}$ is the unique matrix such that $\mathbf{M}\mathbf{M}^{+}\mathbf{M}=\mathbf{M}$, $\mathbf{M}^{+}\mathbf{M}\mathbf{M}^{+}=\mathbf{M}^{+}$, with $\mathbf{M}^{+}\mathbf{M}$ and $\mathbf{M}\mathbf{M}^{+}$ Hermitian [42]. The spectral radius $\rho(\mathbf{M})$ of a matrix $\mathbf{M}$ is the largest modulus among its eigenvalues.

A Hilbert space is a complete normed vector space where the norm arises from an inner product. A linear operator $T:X\rightarrow Y$ between Hilbert spaces is bounded if it has finite operator norm, i.e. $\|T\|_{op}=\sup_{\|g\|_{X}\leq 1}\|Tg\|_{Y}<\infty$. We denote by $\mathbf{T}$ the (infinite) matrix associated with $T$ by some (canonical) orthonormal basis on $H$. An operator is compact if the image of the unit ball in $X$ is relatively compact. Given Hilbert spaces $X,Y$ and a compact operator $T:X\rightarrow Y$, we denote its adjoint by $T^{*}$. The singular numbers $\{\sigma_{n}\}_{n\geq 0}$ of $T$ are the square roots of the eigenvalues of the self-adjoint operator $T^{*}T$, arranged in decreasing order. A $\sigma$-Schmidt pair $\{\boldsymbol{\xi},\boldsymbol{\eta}\}$ for $T$ is a couple of norm $1$ vectors such that: $\mathbf{T}\boldsymbol{\xi}=\sigma\boldsymbol{\eta}$ and $\mathbf{T}^{*}\boldsymbol{\eta}=\sigma\boldsymbol{\xi}$. The Hilbert-Schmidt decomposition provides a generalization of the compact SVD for the infinite matrix of a compact operator $T$ using singular numbers and orthonormal Schmidt pairs: $\mathbf{T}\mathbf{x}=\sum_{n\geq 0}\sigma_{n}\langle\mathbf{x},\boldsymbol{\xi}_{n}\rangle\boldsymbol{\eta}_{k}$ [42]. The spectral norm $\|\mathbf{T}\|$ of the matrix representing the operator $T$ is the largest singular number of $T$. Note that the spectral norm of $\mathbf{T}$ corresponds to the operator norm of $T$.

Let $\ell^{2}$ be the Hilbert space of square-summable sequences over $\Sigma^{*}$, with norm $\|f\|_{2}^{2}=\sum_{x\in\Sigma^{*}}|f(x)|^{2}$ and inner product $\langle f,g\rangle=\sum_{x\in\Sigma^{*}}f(x)g(x)$ for $f,g\in\mathbb{R}^{\Sigma^{*}}$. Let $\mathbb{T}=\{z\in\mathbb{C}:|z|=1\}$ be the complex unit circle, $\mathbb{D}=\{z\in\mathbb{C}:|z|<1\}$ the (open) complex unit disc. Let $1<p<\infty$, $\mathcal{L}^{p}(\mathbb{T})$ be the space of measurable functions on $\mathbb{T}$ for which the $p$-th power of the absolute value is Lebesgue integrable. For $p=\infty$, we denote with $\mathcal{L}^{\infty}(\mathbb{T})$ the space of measurable functions that are bounded, with norm $\|f\|_{\infty}=\sup\{|f(x)|:x\in\mathbb{T}\}$.

Let $\Sigma$ be a fixed finite alphabet, $\Sigma^{*}$ the set of all finite strings with symbols in $\Sigma$. We use $\varepsilon$ to denote the empty string. Given $p,s\in\Sigma$, we denote with $ps$ their concatenation.

A weighted finite automaton (WFA) of $n$ states over $\Sigma$ is a tuple $A=\langle\boldsymbol{\alpha},\{\mathbf{A}_{a}\},\boldsymbol{\beta}\rangle$, where $\boldsymbol{\alpha},$ $\boldsymbol{\beta}\in\mathbb{R}^{n}$ are the vector of initial and final weights, respectively, and $\mathbf{A}_{a}\in\mathbb{R}^{n\times n}$ is the matrix containing the transition weights associated with each symbol $a$. Every WFA $A$ with real weights realizes a function $f_{A}:\Sigma^{*}\to\mathbb{R}$, i.e. given a string $x=x_{1}\cdots x_{t}\in\Sigma^{*}$, it returns $f_{A}(x)=\boldsymbol{\alpha}^{\top}\mathbf{A}_{x_{1}}\cdots\mathbf{A}_{x_{t}}\boldsymbol{\beta}=\boldsymbol{\alpha}^{\top}\mathbf{A}_{x}\boldsymbol{\beta}$. A function $f:\Sigma^{*}\to\mathbb{R}$ is called rational if there exists a WFA $A$ that realizes it. The rank of the function is the size of the smallest WFA realizing $f$. Given $f:\Sigma^{*}\to\mathbb{R}$, we can consider a matrix $\mathbf{H}_{f}\in\mathbb{R}^{\Sigma^{*}\times\Sigma^{*}}$ having rows and columns indexed by strings and defined by $\mathbf{H}_{f}(p,s)=f(ps)$ for $p,s\in\Sigma^{*}$.

Given a WFA $A=\langle\boldsymbol{\alpha},\{\mathbf{A}_{a}\},\boldsymbol{\beta}\rangle$, the forward matrix of $A$ is the infinite matrix $\mathbf{F}_{A}\in\mathbb{R}^{\Sigma^{*}\times n}$ given by $\mathbf{F}_{A}(p,:)=\boldsymbol{\alpha}^{\top}\mathbf{A}_{p}$ for any $p\in\Sigma^{*}$, while the backward matrix of $A$ is $\mathbf{B}_{A}\in\mathbb{R}^{\Sigma^{*}\times n}$, given by $\mathbf{B}_{A}(s,:)=(\mathbf{A}_{s}\boldsymbol{\beta})^{\top}$ for any $s\in\Sigma^{*}$. Let $\mathbf{H}_{f}$ be the Hankel matrix of $f$, its forward-backward (FB) factorization is: $\mathbf{H}_{f}=\mathbf{F}\mathbf{B}^{\top}$. A WFA with $n$ states is reachable if $\operatorname{rank}(\mathbf{F}_{A})=n$, while it is observable if $\operatorname{rank}(\mathbf{B}_{A})=n$. A WFA is minimal if it is reachable and observable. If $A$ is minimal, the FB factorization is a rank factorization [7].

We recall the definition of the singular value automaton, a canonical form for WFAs [10].

The SVA can be computed with an efficient algorithm relying on the following matrices [11].

Note that if $A$ is an SVA, then the Gramians associated with its FB factorization satisfy $\mathbf{P}_{A}=\mathbf{Q}_{A}=\mathbf{D}$, where $\mathbf{D}$ is the matrix of singular values of its Hankel matrix. The Gramians can alternatively be characterized (and computed [11]) using fixed point equations, corresponding to Lyapunov equations when $|\Sigma|=1$ [27].

Finally, we recall the following definition.

Theorem 2.1 provides us with a way to associate a minimal WFA $A$ with $n$ states to a Hankel matrix $\mathbf{H}$ of rank $n$. The approach we propose to approximate $A$ is to find the WFA corresponding to the matrix that minimizes $\mathbf{H}$ in the spectral norm. We recall the fundamental result of Schmidt, Eckart, Young and Mirsky [17].

Note that a low-rank approximation obtained by truncating the SVD is not in general a Hankel matrix. This is problematic, since $\mathbf{G}$ needs to be Hankel in order to be the matrix of a WFA. Surprisingly, we can obtain a result comparable to the one of Theorem 2.4 while preserving the Hankel property. This is the possible thanks to a theory of optimal approximation called AAK theory [1]. To apply this theory, we will need to rewrite the approximation problem in functional analysis terms. First, we will associate a linear operator to the Hankel matrix. Then, we will use Fourier analysis to reformulate the problem in a function space. A comprehensive presentation of the concepts recalled in this section can be found in [30, 33, 28].

Let $f:\Sigma^{*}\rightarrow\mathbb{R}$ be a rational function, we interpret the corresponding Hankel matrix $\mathbf{H}_{f}$ as the expression of a linear (Hankel) operator $H_{f}:\ell^{2}\rightarrow\ell^{2}$ in terms of the canonical basis. We recall that a Hankel operator $H_{f}$ is bounded if and only if $f\in\ell^{2}$ [11]. This property, together with the fact that we only consider finite rank operators (corresponding to the Hankel matrices of WFAs), is sufficient to guarantee compactness.

To introduce AAK theory, we need to consider a second realization of Hankel operators on complex spaces. Since in this paper we work with two classes of functions – functions over sequences and complex functions – to avoid any confusion we will make explicit the dependence on the complex variable $z=e^{it}$. We start by recalling a few fundamental definitions from the theory of complex functions. Note that a function $\phi(z)\in\mathcal{L}^{2}(\mathbb{T})$ can be represented, using the orthonormal basis $\{z^{n}\}_{n\in\mathbb{Z}}$, by means of its Fourier series: $\phi(z)=\sum_{n\in\mathbb{Z}}\widehat{\phi}(n)z^{n}$, with Fourier coefficients $\widehat{\phi}(n)=\int_{\mathbb{T}}\phi(z)\bar{z}^{n}dz,\,n\in\mathbb{Z}$. This establishes an isomorphism between the function $\phi(z)$ and the sequence of the corresponding Fourier coefficients $\widehat{\phi}$. Thus, we can partition the function space $\mathcal{L}^{2}(\mathbb{T})$ into two subspaces.

It is possible to define Hardy spaces also on the open unit disc $\mathbb{D}$.

Interestingly, $\mathcal{H}^{p}(\mathbb{D})$ and $\mathcal{H}^{p}$ can be canonically identified by associating a function $\phi(z)\in\mathcal{H}^{p}(\mathbb{D})$ with its limit on the boundary, which is a function in $\mathcal{H}^{p}$ (a proof can be found in [30]). Thus, we will make no difference between those functions in the unit disc and their boundary value on the circle.

We can now embed the sequence space $\ell^{2}$ into $\ell^{2}(\mathbb{Z})$ by “duplicating” each vector, i.e. by associating $\boldsymbol{\mu}=(\mu_{0},\mu_{1},\dots)\in\ell^{2}$ to $\boldsymbol{\mu}^{(2)}=(\dots,\mu_{1},\mu_{0},\mu_{1},\dots)\in\ell^{2}(\mathbb{Z})$. Then, we can use the Fourier isomorphism to map the vector $\boldsymbol{\mu}^{(2)}\in\ell^{2}(\mathbb{Z})$ to the function space $\mathcal{L}^{2}(\mathbb{T})$. In this way each vector $\boldsymbol{\mu}\in\ell^{2}$ corresponds to two functions in the Hardy spaces:

This leads to an alternative characterization of Hankel operators in Hardy spaces.

If $H_{\phi}$ is a bounded operator, we can consider without loss of generality $\phi(z)\in\mathcal{L}^{\infty}(\mathbb{T})$. This is a consequence of Nehari’s theorem [29], whose formulation can be found in Appendix A, together with more details about the two definitions of Hankel operators. We remark that a Hankel operator has infinitely many different symbols, since $H_{\phi}=H_{\phi+\psi}$ for $\psi(z)\in\mathcal{H}^{\infty}$.

We remark that the poles of a complex function $f$ correspond to the zeros of $1/f$. The following result of Kronecker relates finite-rank infinite Hankel matrices to rational functions.

We state as remark an important takeaway from this section.

We can introduce now the main result of Adamyan, Arov and Krein [1]. The theorem, stated for Hankel operators over Hardy spaces, shows that for infinite dimensional Hankel matrices the constraint of preserving the Hankel property does not affect the achievable approximation error.

We denote with $\mathcal{R}_{k}\subset\mathcal{H}^{\infty}_{-}$ the set of strictly proper rational functions of rank $k$, and we consider the set:

We can reformulate the theorem in terms of symbols.

The solutions of Theorem 2.8 and 2.9 are strictly related (proof in Appendix A).

We state as corollary the key point of the proof of AAK Theorem, that provides us with a practical way to find the best approximating symbol.

To apply AAK theory to the approximate minimization problem, we consider only automata with real weights, defined over a one-letter alphabet. In this case, the free monoid generated by the single letter can be identified with $\mathbb{N}$, and canonically embedded into $\mathbb{Z}$. This passage is fundamental to use Fourier analysis and the isomorphism that leads to Theorem 2.8 and 2.9. Unfortunately, this idea cannot be directly generalized to bigger alphabets, since in this case we would obtain a free non-abelian monoid (not identifiable with $\mathbb{Z}$).

Theorem 2.8 requires the Hankel operator $H$ to be bounded. To ensure that a minimal WFA $A=\langle\boldsymbol{\alpha},\mathbf{A},\boldsymbol{\beta}\rangle$ satisfies this condition, we assume $\rho(\mathbf{A})<1$, where $\rho$ is the spectral radius of $\mathbf{A}$ [11]. As a matter of fact, to guarantee the boundness of the Hankel operator it is enough that the considered WFA computes a function $f\in\ell^{2}$ [11]. However, the stricter assumption on the spectral radius is needed when computing the symbol associated to a WFA. This condition directly implies the existence of the SVA, and of the Gramian matrices $\mathbf{P}$ and $\mathbf{Q}$, with $\mathbf{P}=\mathbf{Q}$ diagonal [11]. We assume that $A=\langle\boldsymbol{\alpha},\mathbf{A},\boldsymbol{\beta}\rangle$ is in SVA form. In this case, given the size of the alphabet, the Hankel matrix $\mathbf{H}$ is symmetric, so $\mathbf{A}=\mathbf{A}^{\top}$. Moreover, if we denote with $\lambda_{i}$ the $i$-th non-zero eigenvalue of $\mathbf{H}$, and we consider the coordinates of $\boldsymbol{\alpha}$ and $\boldsymbol{\beta}$, we have that $\boldsymbol{\alpha}_{i}=\operatorname{sgn}(\lambda_{i})\boldsymbol{\beta}_{i}$, where $\operatorname{sgn}(\lambda_{i})=\lambda_{i}/|\lambda_{i}|$.

For example, we note that a minimal GPA computes a function $f\in\ell^{1}$, so the condition on $\rho(\mathbf{A})$ is automatically satisfied by this class of WFAs [11]. Possible relaxations of the spectral radius assumption are discussed in Appendix C, together with an alternative method to find the optimal spectral-norm approximation of a Hankel matrix without extracting a WFA.

Finally, in this paper we only consider automata with weights in $\mathbb{R}$, though results remain true for complex numbers. The method we present can be easily extended to vector-valued automata [35], but the solution to the optimal approximation problem will not be unique [33].

Let $A=\langle\boldsymbol{\alpha},\mathbf{A},\boldsymbol{\beta}\rangle$ be a minimal WFA with $n$ states in SVA form, defined over a one-letter alphabet. Let $\mathbf{H}$ be the Hankel matrix of $A$, we denote with $\sigma_{i}$, for $0\leq i<n$, the singular numbers. Given a target number of states $k<n$, we say that a WFA $\widehat{A}_{k}$ with $k$ states solves the optimal spectral-norm approximate minimization problem if the Hankel matrix $\mathbf{G}$ of $\widehat{A}_{k}$ satisfies $\|\mathbf{H}-\mathbf{G}\|=\sigma_{k}(\mathbf{H})$. Note that the content of the “optimal spectral-norm approximate minimization” is equivalent to the problem solved by Theorem 2.8, with the exception that here we insist on representing the inputs and outputs of the problem effectively by means of WFAs. Based on the AAK theory sketched in Section 2.3, we draw the following steps:

1. 1.

   Compute a symbol $\phi(z)$ for $H$ using Remark 2. We obtain the negative Fourier coefficients of $\phi(z)$ and derive its Fourier series.

2. 2.

   Compute the optimal symbol $\psi(z)$ using Corollary 2. The main challenge here is to find a suitable representation for the functions $\psi(z)$ and $e(z)=\phi(z)-\psi(z)$. We define them in terms of two auxiliary WFAs. The key point is to select constraints on their parameters to leverage the properties of weighted automata, while still keeping the formulation general.

3. 3.

   Extracting the rational component by solving for $g(z)$ in Corollary 1. This step is arguably the most conceptually challenging, as it requires to identify the position of the function’s poles. In fact, we know from Theorem 2.6 that $g(z)$ has $k$ poles, all inside the unit disc.

4. 4.

   Find a WFA representation for $g(z)$. Since in Step 2 we parametrized the functions using WFAs, the expression of $g(z)$ directly reveals the WFA $\widehat{A}_{k}$.

In the following sections we will consider a minimal WFA $A=\langle\boldsymbol{\alpha},\mathbf{A},\boldsymbol{\beta}\rangle$ with $n$ states in SVA form, defined over a one-letter alphabet $\Sigma=\{a\}$, its Hankel matrix $\mathbf{H}$, corresponding to the bounded operator $H$, and the singular numbers $\sigma_{i}$, for $0\leq i<n$. Let $f:\Sigma^{*}\rightarrow\mathbb{R}$ be the function realized by $A$. We denote by $x$ the string where $a$ is repeated $x$ times, so we have $f(x)=\boldsymbol{\alpha}^{\top}\mathbf{A}^{x}\boldsymbol{\beta}$.