Lower-bound on Sobolev norm of function on $(d-1)$-dimensional sphere, whose sign has been fixed at $n$ points

Question

---

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}. $$

Answer 1

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.