A Tree Labeling Problem with an Application to Optimal Approximation of Continuous Functions

V. V. Galatenko

M. V. Lomonosov Moscow State University

Abstract: We state a tree labeling problem, give an algorithm for solving it, and discuss some complexity characteristics of the algorithm. Furthermore, we discuss applications of these results to the approximation of a continuous function with given accuracy by linear combinations of characteristic functions of dyadic intervals with as few summands as possible. We also touch upon issues concerning tree-aided signal discretization.

Keywords: trees labeling, complexity, function approximation, $n$-term approximation, signal discretization.

UDC: 519.172.1+517.518.3

Received: 24.06.2010
Revised: 16.10.2010

DOI: 10.4213/mzm8827

 English version: Mathematical Notes, 2012, 91:1, 22–33

Bibliographic databases:

• 
• 
• 
• 
•