Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs
type: Item
instance of: scholarly article
title: Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs
zbMATH Open document ID: 1456.62052
DOI: 10.1214/17-AOS1656
author: Zhou Fan
author: Leying Guan
published in: The Annals of Statistics
publication date: 2018-10-25T00:00:00Z
full work available at URL: https://arxiv.org/abs/1703.01421
full work available at URL: https://projecteuclid.org/euclid.aos/1536631272
review text: 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.
Mathematics Subject Classification ID: 62G05
Mathematics Subject Classification ID: 62G10
zbMATH DE Number: 6965686
zbMATH Keywords: approximation algorithm
zbMATH Keywords: graph cut
zbMATH Keywords: effective resistance
zbMATH Keywords: total-variation denoising
zbMATH Keywords: change-point detection
reviewed by: Jaromír Antoch
describes a project that uses: LAMG
describes a project that uses: PDCO
describes a project that uses: MAXFLOW
MaRDI profile type: Publication
arXiv ID: 1703.01421
cites work: On combinatorial testing problems
cites work: Detection of an anomalous cluster in a network
cites work: Searching for a trail of evidence in a maze
cites work: Near-Optimal Detection of Geometric Objects by Fast Multiscale Methods
cites work: Cluster detection in networks using percolation
cites work: Algorithms for the optimal identification of segment neighborhoods
cites work: Risk bounds for model selection via penalization
cites work: A Bayesian Analysis for Change Point Problems
cites work: Q3750011
cites work: Simultaneous analysis of Lasso and Dantzig selector
cites work: Minimal penalties for Gaussian model selection
cites work: Q4787357
cites work: Consistencies and rates of convergence of jump-penalized least squares estimators
cites work: Image recovery via total variation minimization and related problems
cites work: Atomic decomposition by basis pursuit
cites work: Estimating the Current Mean of a Normal Distribution which is Subjected to Changes in Time
cites work: On the prediction performance of the Lasso
cites work: Local extremes, runs, strings and multiresolution. (With discussion)
cites work: Wedgelets: Nearly minimax estimation of edges
cites work: Ideal spatial adaptation by wavelet shrinkage
cites work: Large-Scale Simultaneous Hypothesis Testing
cites work: Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
cites work: Minimizing Effective Resistance of a Graph
cites work: The Split Bregman Method for L1-Regularized Problems
cites work: Multiple Change-Point Estimation With a Total Variation Penalty
cites work: A new approach to the minimum cut problem
cites work: Optimal Detection of Changepoints With a Linear Computational Cost
cites work: Minimax theory of image reconstruction
cites work: Detecting multiple change-points in the mean of Gaussian process by model selection
cites work: Lean Algebraic Multigrid (LAMG): Fast Graph Laplacian Linear Solver
cites work: Q4878667
cites work: Locally adaptive regression splines
cites work: Optimal approximations by piecewise smooth functions and associated variational problems
cites work: Properties and refinements of the fused Lasso
cites work: Nonlinear total variation based noise removal algorithms
cites work: Graph Sparsification by Effective Resistances
cites work: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
cites work: Selective inference with a randomized response
cites work: Q4864293
cites work: Sparsity and Smoothness Via the Fused Lasso
cites work: The solution path of the generalized lasso
cites work: On the conditions used to prove oracle results for the Lasso
cites work: Q3188036
cites work: Smoothers for Discontinuous Signals
cites work: Estimation of a noisy discrete-time step function: Bayes and empirical Bayes approaches
cites work: Estimating the number of change-points via Schwarz' criterion
cites work: Q3497042
cites work: Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators
description: scientific article