PAST INPUT RECONSTRUCTION IN FAST LEAST-SQUARES ALGORITHMS

This paper solves the following problem: Given the computed variables in a fast least-squares prediction algorithm, determine all past input sequences that would have given rise to the variables in question, Th is problem is motivated by the backward consistency approach to numeri cal stability in this algorithm class; the set of reachable variables in exact arithmetic is known to furnish a stability domain, Our proble m is equivalent to a first- and second-order interpolation problem int roduced by Mullis and Roberts and studied by others, Our solution diff ers in two respects. First, relations to classical interpolation theor y are brought out, which allows us to parametrize all solutions. Bypro ducts of our formulation are correct necessary and sufficient conditio ns for the problem to be solvable, in contrast to previous works, whos e claimed sufficient conditions are shown to fall short, Second, our s olution obtains any valid past input as the impulse response of an app ropriately constrained orthogonal filter, whose rotation parameters de rive in a direct manner from. the computed variables in a fast least-s quares prediction algorithm, Formulas showing explicitly the form of a ll valid past inputs should facilitate the study of what past input pe rturbation is necessary to account for accumulated arithmetic errors i n this algorithm class. This, in turn, is expected to have an impact i n studying accuracy aspects in fast least-squares algorithms.