On finding an upper bound on the error of a sparse approximation 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?
 A: 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$.
