On finding an upper bound on the error of a sparse approximation

Question

I posted this question on math.stackexchange earlier, but didn't see any response. So, I am posting it here, in case someone else has an answer. Original question: https://math.stackexchange.com/questions/4443845/on-finding-an-upper-bound-on-the-error-of-a-sparse-approximation

---

$x \in R^n$ is a non-negative vector such that $ \sum_{i=1}^n x_i = 1$ ($\forall i, 0 \le x_i \le 1$).

The components are ordered: $x_1 \ge x_2 \ldots \ge x_n$.

We are also given : $ \sum_{i=1}^n x_i^2 \ge t$ for some constant $t$ ($0 \le t \le 1$).

Clearly, the larger the constant $t$, the more concentrated the components $x_i$ are going to become.

I want to make a claim on the approximate sparsity of $x$. In other words, I want to place an upper bound on the total energy taken up by the smallest $(n-K)$ components.

Say, something like : there exists an integer $K(t)$, $1 \le K \le n$, such that

$$ \sum_{i =K+1}^n x_i^2 \le \phi(t) $$ where $\phi(t)$ is some decreasing function of $t$.

How do I get such a relation?

Answer 1

Take any integer $k\in[1,n]$ and any $t\in[1/2,1]$. Consider the problem of finding the exact upper bound on $\sum_{i=k+1}^n x_i^2$ given the conditions \begin{equation*} x_1\ge\cdots\ge x_n\ge0,\quad\sum_{i=1}^n x_i=1,\quad\sum_{i=1}^n x_i^2=t. \tag{10}\label{10} \end{equation*} By continuity and compactness, there is a maximizer $x=(x_1,\dots,x_n)$ of $\sum_{i=k+1}^n x_i^2$ given the conditions \eqref{10}. In what follows, let $x$ be such a maximizer (unless specified otherwise).

The cases when $n=k$ or $t=1$ are trivial: then conditions \eqref{10} imply $\sum_{i=k+1}^n x_i^2=0$. So, assume $n\ge k+1$ and $t\in[0,1)$. Then there is some integer $i\in[k+1,n]$ such that $x_i>0$. Indeed, if $x_1=\sqrt t$, $x_2=\cdots=x_{k+1}=\dfrac{1-\sqrt t}k$, and $x_i=0$ for $i>k+1$, then conditions \eqref{10} hold and $\sum_{i=k+1}^n x_i^2>0$. So, \begin{equation*} \sum_{i=k+1}^n x_i^2>0 \tag{11}\label{11} \end{equation*} for the maximizer $x=(x_1,\dots,x_n)$ of $\sum_{i=k+1}^n x_i^2$.

To obtain a contradiction, suppose that the maximizer $x=(x_1,\dots,x_n)$ is such that the $x_i$'s take at least three distinct values $u_1,u_2,u_3$ with respective multiplicities $m_1,m_2,m_3$ such that $u_1>u_2>u_3>0$. Without loss of generality, the "run" $R_3:=\{i\colon x_i=u_3\}$ of the repeated value $u_3$ is the rightmost run of a strictly positive value; that is, if $i_3:=\max R_3$, then $x_i=0$ for all $i>i_3$. So, in view of \eqref{11}, $i_3\ge k+1$. Let us apply respective infinitesimal changes $\dfrac{du_1}{m_1},\dfrac{du_2}{m_2},\dfrac{du_3}{m_3}$ to $u_1,u_2,u_3$ such that \begin{equation*} du_1+du_2+du_3=0,\quad u_1du_1+u_2du_2+u_3du_3=0,\quad u_3du_3>0; \tag{12}\label{12} \end{equation*} to satisfy conditions \eqref{12}, let \begin{equation*} du_3>0,\quad du_2:=-\frac{u_1-u_3}{u_1-u_2}\,du_3, \quad du_1:=\frac{u_2-u_3}{u_1-u_2}\,du_3. \end{equation*} Then the conditions \eqref{10} will continue to hold, for $u_1+\dfrac{du_1}{m_1},u_2+\dfrac{du_2}{m_2},u_3+\dfrac{du_3}{m_3}$ in place of $u_1,u_2,u_3$, whereas the target sum $\sum_{i=k+1}^n x_i^2$ will strictly increase (since $i_3\ge k+1$), which will contradict the assumption that $x=(x_1,\dots,x_n)$ is a maximizer.

Thus, the $x_i$'s take at most two distinct values $u,v$ such that $u\ge v>0$. So, for some integers $j\in[1,k]$ and $l\ge1$ we have \begin{equation*} x_1=\cdots=x_j=u,\quad x_{j+1}=\cdots=x_{k+l}=v, \quad x_i=0\text{ for }i>k+l. \end{equation*} If $j\ge2$, then the condition $\sum_{i=1}^n x_i=1$ in \eqref{10} implies $u<\frac12$ and hence $x_i<\frac12$ for all $i$, so that $\sum_{i=1}^n x_i^2<\frac12\,\sum_{i=1}^n x_i=\frac12\le t$, which contradicts the condition $\sum_{i=1}^n x_i^2=t$ in \eqref{10}. So, $j=1$ and we have \begin{equation*} x_1=u,\quad x_2=\cdots=x_{k+l}=v, \quad x_i=0\text{ for }i>k+l. \end{equation*} Now the equations $\sum_{i=1}^n x_i=1$ and $\sum_{i=1}^n x_i^2=t$ become $u+(k+l-1)v=1$ and $u^2+(k+l-1)v^2=t$. Solving the latter two equations for $u$ and $v$, we see that the maximum of $\sum_{i=k+1}^n x_i^2$ given the conditions \eqref{10} is of the form \begin{equation*} M_k(l):=\frac l{(k+l)^2}\,\Big(1-\sqrt{1-\frac{k+l}{k+l-1}\,(1-t)}\Big)^2 \end{equation*} for some integer $l\ge1$. We shall assume that $n\ge k+l$, not to let $n$ play an essential role.

Now, to get the maximum of $\sum_{i=k+1}^n x_i^2$ given \eqref{10}, it remains to maximize $M_k(l)$ in $l$. This maximization seems rather complicated to be done explicitly, even though the defining expression for $M_k(l)$ is algebraic.

Instead of the exact maximization of $M_k(l)$ in $l$, let us get a good upper bound on $M_k(l)$. Since $\frac{k+l}{k+l-1}\le2$ and $\sqrt z\ge z$ for $z\in[0,1]$, we have \begin{equation*} M_k(l)\le\frac l{(k+l)^2}\,2^2(1-t)^2\le\frac{(1-t)^2}k. \end{equation*}

---

In my other answer on this page, it was shown (see (3) there, with $s=t$ when $t\in[1/2,1]$) that no upper bound on $\sum_{i=k+1}^n x_i^2$ given \eqref{10} can be better than $\asymp \frac{(1-t)^2}k$ for $t\in[1/2,1]$. It was also shown in that answer that the the optimal upper bound on $\sum_{i=k+1}^n x_i^2$ is $\asymp\dfrac1k$ for $t\in[0,1/2]$.

Thus, the optimal upper bound on $\sum_{i=k+1}^n x_i^2$ given \eqref{10} is $\asymp \frac{(1-t)^2}k$ for all $t\in[0,1]$.

Answer 2

Take any integer $k\ge1$ and any $t\in[0,1]$. Let us show that \begin{equation*} \sum_{i=k+1}^n x_i^2\le\frac{1-t}k. \tag{0}\label{0} \end{equation*}

The key here is

Lemma 1: For any $u\in[0,1)$ and any $x\in[0,1]$, \begin{equation*} x^2\,1(x\le u)\le\frac u{1-u}\,(x-x^2). \tag{1}\label{1} \end{equation*}

Proof: Let $d(x):=d_u(x):=\dfrac u{1-u}\,(x-x^2)-x^2\,1(x\le u)$, the difference between the right- and left-hand sides of \eqref{1}. On the interval $[0,u]$, the function $d$ is concave. Therefore and because $d(0)=0=d(u)$, it follows that $d\ge0$ on $[0,u]$. That $d\ge0$ on $(u,1]$ is trivial. So, $d\ge0$ on $[0,1]$. That is, \eqref{1} does hold. $\quad\Box$

By Lemma 1 and in view of the conditions $\sum_{i=1}^n x_i=1$ and $\sum_{i=1}^n x_i^2\ge t$, \begin{equation*} \sum_{i=1}^n x_i^2\,1(x_i\le u)\le\frac u{1-u}\,\Big(\sum_{i=1}^n x_i-\sum_{i=1}^n x_i^2\Big) \le\frac u{1-u}\,(1-t). \tag{2}\label{2} \end{equation*} Also, for any $i\in[n]:=\{1,\dots,n\}$, the conditions $x_1\ge\cdots\ge x_n\ge0$ imply that \begin{equation*} ix_i\le\sum_{j=1}^i x_j\le\sum_{j=1}^n x_j=1. \end{equation*} So, for $i\in[n]$ and any integer $k\ge1$ we have the implication \begin{equation*} i\ge k+1\implies x_i\le\frac1i\le\frac1{k+1}. \end{equation*} So, by \eqref{2} with $u=u_k:=\dfrac1{k+1}$, \begin{equation*} \sum_{i=k+1}^n x_i^2\le\sum_{i=1}^n x_i^2\,1(x_i\le u_k) \le\frac{u_k}{1-u_k}\,(1-t)=\frac{1-t}k, \end{equation*} so that inequality \eqref{0} follows.

---

The bound $\dfrac{1-t}k$ in \eqref{0} is of the optimal order $\asymp\dfrac1k$ for $t\in[0,1/2]$. Indeed, take any $t\in[0,1]$ and any integer $l\ge1$. Let $p:=k+l-1$, so that $p\ge1$. Let $s:=\max(\frac12,t)$. Let $u:=\sqrt s$ and $v:=\dfrac{1-\sqrt s}p$. Suppose that $n\ge p+1$, $x_1=u$, $x_2=\cdots=x_{p+1}=v$, and $x_i=0$ for $i>p+1$. Then $(p+1)\sqrt s\ge2\sqrt{\frac12}>1$ and hence $u>v$, so that the conditions $1\ge x_1\ge\cdots\ge x_n\ge0$ holds. The conditions $\sum_{i=1}^n x_i=1$ and $\sum_{i=1}^n x_i^2\ge t$ hold as well. Moreover, \begin{equation} \sum_{i=k+1}^n x_i^2=lv^2=(1-\sqrt s)^2\frac l{(k+l-1)^2} \\ \ge(1-\sqrt s)^2\frac l{(k+l)^2} \ge\frac{(1-s)^2}{16k} \tag{3}\label{3} \end{equation} if $l=k$. If now $t\in[0,1/2]$, then $s=1/2$ and hence \begin{equation} \sum_{i=k+1}^n x_i^2 \ge\frac1{64k}\asymp\dfrac1k, \end{equation} as claimed.

---

In my other answer on this page, it will be shown, based on another idea, that for $t\in[1/2,1]$ -- and hence for all $t\in[0,1]$ -- the optimal upper bound on $\sum_{i=k+1}^n x_i^2$ is of the order $\dfrac{(1-t)^2}k$.