Denoising Flows on Trees

作者：Chatterjee Sabyasachi^*; Lafferty John

来源：IEEE Transactions on Information Theory, 2018, 64(3): 1767-1783.

DOI：10.1109/TIT.2017.2782369

• Isotonic regression
• least squares estimator
• minimax lower bounds
• signal denoising

We study the estimation of flows on trees, a structured generalization of isotonic regression. A tree flow is defined recursively as a positive flow value into a node that is partitioned into an outgoing flow to the children nodes, with some amount of the flow possibly leaking outside. We study the behavior of the least squares estimator for flows, and the associated minimax lower bounds. We characterize the risk of the least squares estimator in two regimes. In the first regime, the diameter of the tree grows at most logarithmically with the number of nodes. In the second regime, the tree contains many long paths. The results are compared with known risk bounds for isotonic regression. In the many long paths regime, we find that the least squares estimator is not minimax rate optimal for flow estimation.

• 出版日期2018-3