Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs (Q1990576)

Let \(G=(V, E)\) be a known undirected graph with vertices \(V\) and edge set \(E\). At each vertex \(i\) an unknown signal value \(\mu_{0,i}\) is observed with noise, resulting in \(Y_i = \mu_{0,i} +\epsilon_i\), \(\epsilon_i\) being iid normal \(N(0,\sigma^{2})\). Main problem is to estimating the true signal vector \(\mu_{0}\) from observed data when \(\mu_{0}\) is (can be well approximated by) a piecewise-constant signal over \(G\). The focus is on \(l_0\)-edge-denoising which seeks to estimate \(\mu_{0}\) by the values \(\mu\in R_n\) minimizing the residual squared error plus a penalty for each edge. The combinatorial nature of the problem render exact minimization of the objectives computationally intractable for general graphs. However, primary purpose is to show that approximate minimization is sufficient to obtain statistically rate-optimal guarantees. Main results are as follows. \begin{itemize} \item A polynomial-time algorithm yielding approximate minimizers of considered problems that achieve, up to constant factors, the same statistical risk as the exact minimizers. \item It is shown that for any graph \(G\) suggested estimate \(\hat\mu_{0}\) an ``edge-sparsity'' oracle inequality, and that obtained risk bound is rate-optimal in a minimax sense over the edge-sparse signal class up to a multiplicative factor depending on the mean vertex degree of \(G\). \item Properties of an alternative minimizing corresponding \(l_1\)/total-variation relaxation are given. \item Previous results are generalized for edge-weighting for inhomogeneous graphs. \end{itemize} Simulations and simulated applications illustrate chosen approach. All proofs are postponed to the Appendix available on the Internet.