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?



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


