On the nuclear norm heuristic for a Hankel matrix completion problem

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 are given. Since the setting is deterministic, theories based on stochastic assumptions for low-rank matrix recovery do not apply in the considered situation. A 'certificate' which guarantees the success of the matrix completion task 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.