Structure-Blind Signal Recovery
We consider the problem of recovering a signal observed in Gaussian noise. If the set of signals is convex and compact, and can be specified beforehand, one can use classical linear estimators that achieve a risk within a constant factor of the minimax risk. However, when the set is unspecified, designing an estimator that is blind to the hidden structure of the signal remains a challenging problem. We propose a new family of estimators to recover signals observed in Gaussian noise. Instead of specifying the set where the signal lives, we assume the existence of a well-performing linear estimator. Proposed estimators enjoy exact oracle inequalities and can be efficiently computed through convex optimization. We present several numerical illustrations that show the potential of the approach.
The paper studies theoretically linear filters for signal denoising. An interesting formulation of the problem is obtained under the assumption that the signal has a regular component in an unknown shift-invariant linear subspace, a bounded free component and an i.i.d. Gaussian noise component. It is proposed that the recovery formulation that constrains or penalizes l1 norm in the Fourier space, under some technical conditions, possess guaranteed performance bounds. The goal here is to obtain an estimator achieving a risk within a constant additive bound (called the price of adaptation) of that of the optimal linear estimator. The paper improves upon previous works [10,5] providing tighter additive bounds. Penalized recovery version does not need to know the filter norm parameter in advance.
I’ve indicated below that I am not confident in this topic, please take my questions with ease. Clarity A general question about blind filtering: Is it indeed the case that the knowledge about the set of signals X cannot be obtained / learned in some applications or it is more that it is difficult to describe? In the case of shift-invariant subspaces the description does not seem to be a problem, it is given by equations (6). Small-error linear filters. It was unclear why the signal is restricted to the support interval [0 n] but its recovery is requested on the interval [-m 2m]. Does it mean in particular that there are m samples of pure noise available? How does this support assumption combine with shift-invariance equations (6)? The simplicity assumption is designed such that the total recovery error (5) does not depend on the length of the sequence, and the filter size must grow proportionally to the sequence support. It does not seem realistic.  While the main theoretical contributions were presented for the “sequential” filters – only signals to the left on the axis are participating, the experimental results are presented in the different setting – full 2D linear filters. Is this difference not essential? Do the bounds continue to hold? There are many image denoising techniques in the literature. If we compare to TV-denoising, the prior is imposed on the reconstructed signal, whereas in the proposed method it is imposed on the filter. Can the methods be theoretically / experimentally compared? Since the reconstruction requires to solve an optimization problem, is the special structure of requesting a linear filter is still well-justified / beneficial in practice? While the discussion section dives deeper in a specific direction, a concluding section discussing the theoretical results and experiments overall is missing. Technical Line 56: a new notation seems to be introduced, in which case “may be written as” is not appropriate. Line 75: \phi^0 Line 93: \Delta^\tau is not defined – compositional power?  ***************************  I would recommend to the authors to improve on accessibility of their work. While presented results are really theoretically interesting, understanding them is not easy. In particular the assumptions made for the theory to hold are by far non-trivial. Try to show exemplar cases where these assumptions do hold and if possible explain more their meaning. Do these assumptions translate to something that can be calculated post-optimization so that a provable bound for a quality of reconstruction of a given instance can be computed? It would be also beneficial if the handling of different kinds of filters w.r.t. time axis was more uniform across the paper. Despite the authors claim the results are easily extendible, it is not straightforward to see how the assumptions and the bounds should extend to 2D full filters. The question regarding optimization-based recovery of linear filter versus optimization-based recovery of the signal directly was not fully answered in the rebuttal. In particular problem (8) can be rewritten with a substitute variable \hat x = \varphi * y, which will result in a special regularized on \hat x. While the method does not need to know the structure (the shift-invariant linear subspace) of the signal, in many applications such structure, e.g. appropriate basis can be learned from the training data. The advantage of doing blind recovery in this setting is not of that high practical interest in my opinion.