On the Nuclear Norm heuristic for a Hankel matrix Recovery Problem
Provides theoretical justification for nuclear norm heuristic in a deterministic low-rank matrix recovery problem relevant to system identification.
The paper investigates whether the nuclear norm heuristic can recover an impulse response from a stable single-real-pole system given partial Hankel matrix entries, and constructs a certificate to guarantee recovery. Experiments extend the analysis to more general settings.
This note addresses the question if and why the nuclear norm heuristic can recover an impulse response generated by a stable single-real-pole system, if elements of the upper-triangle of the associated Hankel matrix were given. Since the setting is deterministic, theories based on stochastic assumptions for low-rank matrix recovery do not apply here. A 'certificate' which guarantees the completion is constructed by exploring the structural information of the hidden matrix. Experimental results and discussions regarding the nuclear norm heuristic applied to a more general setting are also given.