1
$\begingroup$

Let $\mathbb S_{d-1} := \{x \in \mathbb R^d \mid x^\top x = 1\}$ be $(d-1)$-dimensional sphere in $\mathbb R^d$ and let $\sigma_d$ be the uniform distribution on $\mathbb S_{d-1}$. Let $x_1,\ldots,x_n$ be sampled iid according to $\sigma$ and let $y_1,\ldots,y_n \in \{\pm 1\}$ be fixed. Consider a continuously differentiable $L^2$ function $f: \mathbb R^d \to \mathbb R$. Let $\nabla_{\mathbb S_{d-1}} f:\mathbb S_{d-1} \to T\mathbb S_{d-1}$ be the spherical gradient of $f$, defined for each $x \in \mathbb S_{d-1}$ by $$ \nabla f_{\mathbb S_{d-1}} (x) := P_{T_x\mathbb S_{d-1}}(\nabla f(x)) = P_{x^\perp}(\nabla f (x)) = \nabla f(x) - (x^\top\nabla f(x))x. $$ Finally, define the Sobolev norm $\|\nabla_{\mathbb S_{d-1}} f\|_{L^2(\sigma_d)} := (\int_{\mathbb S_{d-1}}\|\nabla_{\mathbb S_{d-1}}f\|^2d\sigma(x))^{1/2}$.

Question. Given that $f(x_i) = y_i$ for all $i=1,\ldots,n$, what is a good lower-bound for $\|\nabla_{\mathbb S_{d-1}} f\|_{L^2(\sigma_d)}$ which holds w.h.p over the choice of $x_1,\ldots,x_n$?

My attempt via Poincaré inequality

By the Poincaré inequality for the sphere, we have $$ \|\nabla_{\mathbb S_{d-1}} f\|_{L^2(\sigma_d)} \gtrsim \sqrt{d} \|f-\overline{f}\|_{L^2(\sigma)}, \tag{1} $$

where $\overline{f} := \int_{\mathbb S_{d-1}}f(x)d\sigma_d(x)$ is the average value of $f$.

  • I'm stuck at using the given data (i.e $f(x_i) = y_i \;\forall i$) to lower-bound the RHS of the above inequality.

Complete solution for the linear case

For example if $f(x) = w^\top x$ for some $w \in \mathbb R^d$. Then $$ \|f-\overline{f}\|_{L^2(\sigma)}^2 = \|f\|_{L^2(\sigma)}^2 = \int_{\mathbb S_{d-1}}(w^\top x)^2d\sigma(x) = \|w\|^2\mathbb E_\sigma[xx^\top] = \frac{\|w\|^2}{d}. $$

Now the constraints $y_i = f(x_i)$ for all $i$, can be written as $Xw = y$, where $X$ is an $n \times d$ matrix with $i$th row $x_i$ and $y$ is a column vector of length $n$, and $i$th entry $y_i$. Suppose $n \le \delta d$ with $\delta \in (0, 1)$. By basic linear algebra, $\|w\|^2 \ge \|w_{OLS}\|^2$, where $w_{OLS} := X^\top(XX^\top)^{-1}y$ is the least squares solution (due to Gauss and Legendre) to the equation $Xw=y$. Thus for any other solution $w$, we have $$ \|w\|^2 \ge \|w_{OLS}\|^2 = y^\top (XX^\top)^{-1} y \ge \frac{\|y\|^2}{ \lambda_\min(XX^\top)} = \Omega(1)\cdot \|y\|^2 $$ w.p $1-Ae^{-Bd}$, for universal constants $A,B>0$ (independent of $n$ and $d$).

Combining with (1), we obtain that w.p $1-Ae^{-Bd}$,

$$ \|\nabla_{\mathbb S_{d-1}} f\|_{L^2(\sigma)} \gtrsim \|y\| = \sqrt{n}. $$

$\endgroup$
3
  • $\begingroup$ If d>2 the Sobolev norm is not strong enough to allow pointwise evaluation, so you will not get any lower bound. $\endgroup$ Nov 26 '20 at 16:47
  • $\begingroup$ @MichaelRenardy Could you kindly expand on your remark a bit ? I'm not strong in functional analysis. Thanks in advance. $\endgroup$
    – dohmatob
    Nov 26 '20 at 16:51
  • $\begingroup$ What he meant is that if $f$ and $g$ are two functions that differ only at finitely many points, then they have the same Sobolev norm. In particular, if you just set $f\equiv 0$ except at the prescribed points, then it is a Sobolev function with Sobolev norm 0 that satisfies your condition. When $d \leq 2$ by Morrey's inequality your equivalence class of Sobolev functions admit a continuous representative. So you can require additionally that $f$ is continuous to rule out such trivialities. But this doesn't work for $d > 2$. $\endgroup$ Feb 3 at 19:28
2
$\begingroup$

For $d \geq 4$, let $\phi$ be a smooth bump function (equals 1 on $B_{1/2}$ and 0 outside $B_1$). Choose small $\epsilon$. Let $f_\epsilon = \sum \phi((x-x_i)/\epsilon) y_i$. You can evaluate

$$ \|\nabla_{\mathbb{S}} f_\epsilon\|_{L^2} = O(\epsilon^{(d-3)/2}) $$

This shows that the only possible lower bound in those cases is 0.

When $d = 2$ I think the optimum is attained by the piecewise linear (in angle $\theta$) interpolation between the points $x_i$ on the circle.

When $d = 3$ the situation is borderline and I am not sure what the answer should be.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer. Now I see the mismatch between what I had in mind and what I ended up asking. It appears to me the function you've constructed does the trick simply bc it has too many "free parameters". In fact to describe the function, one needs one parameter per data point $(x_i,y_i)$, for a total of $n$ parameters. I don't know how to formalize the notion of *dimensionality" or number of "free parameters" of a function. Assuming a suitable, I wonder what's the smallest number of "free parameters" for a function wit sob-norm $\mathcal O(1)$, needed to interpolate the $n$ points while $\endgroup$
    – dohmatob
    Feb 3 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.