Adaptive exact recovery in sparse nonparametric models

We observe an unknown function of <i>d</i> variables <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> , <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>t</mml:mi> <mml:mo>∈</mml:mo> <mml:msup><mml:mrow><mml:mo>[</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>]</mml:mo></mml:mrow> <mml:mi>d</mml:mi></mml:msup> </mml:mrow> </mml:math> , in the Gaussian white noise model of intensity <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>ε</mml:mi> <mml:mo>></mml:mo> <mml:mn>0</mml:mn></mml:mrow> </mml:math> . We assume that the function <i>f</i> is regular and that it is a sum of <i>k</i>-variate functions, where <i>k</i> varies from 1 to <i>s</i> ( <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>1</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>s</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>d</mml:mi></mml:mrow> </mml:math> ). These functions are unknown to us and only a few of them are nonzero. In this article, we address the problem of identifying the nonzero components of <i>f</i> in the case when <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi> <mml:mo>=</mml:mo> <mml:msub><mml:mi>d</mml:mi> <mml:mi>ε</mml:mi></mml:msub> <mml:mo>→</mml:mo> <mml:mi>∞</mml:mi></mml:mrow> </mml:math> as <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>ε</mml:mi> <mml:mo>→</mml:mo> <mml:mn>0</mml:mn></mml:mrow> </mml:math> and <i>s</i> is either fixed or <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>s</mml:mi> <mml:mo>=</mml:mo> <mml:msub><mml:mi>s</mml:mi> <mml:mi>ε</mml:mi></mml:msub> <mml:mo>→</mml:mo> <mml:mi>∞</mml:mi></mml:mrow> </mml:math> , <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>s</mml:mi> <mml:mo>=</mml:mo> <mml:mi>o</mml:mi> <mml:mo>(</mml:mo> <mml:mi>d</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> as <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>ε</mml:mi> <mml:mo>→</mml:mo> <mml:mi>∞</mml:mi></mml:mrow> </mml:math> . This may be viewed as a variable selection problem. We derive the conditions when exact variable selection in the model at hand is possible and provide a selection procedure that achieves this type of selection. The procedure is adaptive to a degree of model sparsity described by the sparsity parameter <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>β</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>(</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo></mml:mrow> </mml:math> . We also derive conditions that make the exact variable selection impossible. Our results augment previous work in this area.