On the total variation regularized estimator over a class of tree graphs

DOI10.1214/18-EJS1519MaRDI QIDQ1711590zbMATH OpenWikidataFDO

Authors Francesco Ortelli, Sara Van De Geer

Publication date 18 January 2019

Published in Electronic Journal of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.01009, https://projecteuclid.org/euclid.ejs/1545210041

zbMATH Keywords

branched path graphcompatibility constantedge lassofused lassoharmonic meanirrepresentable conditionlassooracle inequalitypath graphtotal variation regularizationtree

Mathematics Subject Classification ID

Trees (05C05) Relations of low-dimensional topology with graph theory (57M15) Ridge regression; shrinkage estimators (Lasso) (62J07)

Abstract: We generalize to tree graphs obtained by connecting path graphs an oracle result obtained for the Fused Lasso over the path graph. Moreover we show that it is possible to substitute in the oracle inequality the minimum of the distances between jumps by their harmonic mean. In doing so we prove a lower bound on the compatibility constant for the total variation penalty. Our analysis leverages insights obtained for the path graph with one branch to understand the case of more general tree graphs. As a side result, we get insights into the irrepresentable condition for such tree graphs.

Review text

The approach of \textit{A. S. Dalalyan} et al. [Bernoulli 23, No. 1, 552--581 (2017; Zbl 1359.62295)] is refined for proving a sharp oracle inequality for the total variation regularized estimator (i.e., Fused Lasso) over the path graph. A proof is given of a tight lower bound on the compatibility constant which does not use probabilistic arguments. The approach is generalized to a branched graph and further to tree graphs. In particular the authors generalize the result concerning the irrepresentable condition obtained for the path graph in [\textit{J. Qian} and \textit{J. Jia}, Comput. Stat. Data Anal. 94, 221--237 (2016; Zbl 1468.62161)].

Recommendations

• Reconstruction on trees: exponential moment bounds for linear estimators
• Embedded Trees: Estimation of Gaussian Processes on Graphs with Cycles
• Consistent estimation in general sublinear preferential attachment trees
• Graph estimation for matrix-variate Gaussian data
• Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs
• Estimation of graphical models using the L1,2 norm
• Estimation of graphical models through structured norm minimization
• Regularization on graphs with function-adapted diffusion processes
• Tree and forest weights and their application to nonuniform random graphs

Cites work

• Adaptive estimation of a quadratic functional by model selection.
• Adaptive risk bounds in univariate total variation denoising and trend filtering
• Computing the inverse of a tree's incidence matrix
• Estimation and testing under sparsity. École d'Été de Probabilités de Saint-Flour XLV -- 2015
• Graphs and matrices
• scientific article; zbMATH DE number 5957408 (Why is no real title available?)
• Locally adaptive regression splines
• Minimax estimation via wavelet shrinkage
• On stepwise pattern recovery of the fused Lasso
• On the Inverse of the Sum of Matrices
• On the prediction performance of the Lasso
• On tight bounds for the Lasso
• Pathwise coordinate optimization
• Preconditioning the Lasso for sign consistency
• Sparsity and Smoothness Via the Fused Lasso
• The solution path of the generalized lasso

Cited in

(12)

• A sharp oracle inequality for graph-slope
• Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs
• Multivariate extensions of isotonic regression and total variation denoising via entire monotonicity and Hardy-Krause variation
• Adaptive estimation of multivariate piecewise polynomials and bounded variation functions by optimal decision trees
• Total variation regularized Fréchet regression for metric-space valued data
• Tensor denoising with trend filtering
• Adaptive risk bounds in univariate total variation denoising and trend filtering
• The DFS fused Lasso: linear-time denoising over general graphs
• Logistic regression with total variation regularization
• Adaptive rates for total variation image denoising
• Embedded Trees: Estimation of Gaussian Processes on Graphs with Cycles
• Element-wise estimation error of generalized Fused Lasso

This page was built for publication: On the total variation regularized estimator over a class of tree graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1711590)