Aggregation of Markovian Models -- An Alternating Least Squares Approach

To deal with the problem of state space explosion in Markovian models often compositional modeling and the aggregation of components are used. Several approximate aggregation methods exist which are usually based on heuristics. This paper presents a new aggregation approach for Markovian components which computes aggregates that minimize the difference according to some algebraically defined function which describes the difference between the component and the aggregate. If the difference becomes zero, aggregation is exact and component and aggregate are indistinguishable. Approximate aggregates are computed using an alternating least squares approach which tries to minimize the norm-wise difference between the original component and the aggregate. The approach is extended to generate bounding aggregates which allow one to compute bounds on transient or stationary quantities when the aggregate is embedded in an environment.