0

A Hard thresholding operator $H_k:\mathbb{R}^n\rightarrow \mathbb{R}^n$ is defined as a vector-valued function that maintains the top-k entries of a given vector in an absolute value sense and zero out the rest. As an example $H_2(x)=[-5,0,-3,0]^{\top}$ where $x=[-5,2,-3,1]^{\top}$ and $k=2$. (In a case where two entries are equal we keep the value with smallest index or any other mechanism that make the output unique to have a function)

Question: Is $H_k$ described above a continuous function?

My try:

Given $H_k:\mathbb{R}^n\rightarrow \mathbb{R}^n$, we say that $H_k$ is continuous at $a$ if $H_k(a)$ exists and for all $\epsilon > 0$, there exists a $\delta > 0$ such that $||H_k(x)- H_k(a)||_2 < \epsilon$ whenever $||x-a||_2 < \delta$. Can we satisfy it?

Saeed
  • 175
  • $H_k$ is continuous at some points, but not everywhere. – aschepler Oct 23 '22 at 20:06
  • @aschepler: can you elaborate on your comment, what points make it discontinuous? Is there special class of points that can make it continuous? Can you provide me with a simple counter example that shows it is not continous? – Saeed Oct 23 '22 at 22:35

1 Answers1

1

$H_k$ is not continuous at any point where a "tie-breaker" rule is needed to decide between some coordinates with equal non-zero absolute value. Essentially, arbitrarily small changes in the input vector can force a different tie-breaker decision, which is at roughly a fixed difference in the output vectors.

For one specific counterexample, $H_1: \mathbb{R}^2 \to \mathbb{R}^2$ is discontinuous at $(1,1)$. If $\epsilon=\frac{1}{2}$, and given any $\delta>0$, define

$$\begin{align*} \delta' &= \min\left(\frac{1}{4}, \frac{\delta}{2}\right) \\ x_1 &= (1-\delta', 1) \\ x_2 &= (1, 1-\delta') \end{align*} $$

Then we have $\|x_1-(1,1)\| = \delta' < \delta$, $\|x_2-(1,1)\|=\delta'<\delta$, $H_1(x_1)=(0,1)$, and $H_1(x_2)=(1,0)$. By the triangle inequality, $$\|H_1(x_1)-H_1((1,1))\| + \|H_1(x_2)-H_1((1,1))\| \geq \|H_1(x_1)-H_1(x_2)\| = \sqrt{2}$$ so it is not possible that both $\|H_1(x_1)-H_1((1,1))\| < \epsilon = \frac{1}{2}$ and $\|H_1(x_2)-H_1((1,1))\| < \epsilon = \frac{1}{2}$; $H_1$ cannot be continuous there.

aschepler
  • 9,449
  • can you rewrite your answer using the negation of the definition of continuity. I mean I was trying to show it by saying a function is continuous if for all $\epsilon>0$ there exists a $\delta>0$ such that for all $x \in B(x_0, \delta)$ we have $||H_s(x)-H_s(x_0)||< \epsilon$ and the negation is: there exists $\epsilon>0$ such that for all $\delta>0$, there is an $x \in B(x_0, \delta)$ and we have $||H_s(x)-H_s(x_0)||\geq \epsilon$? – Saeed Oct 24 '22 at 02:56
  • The proof for the counterexample is using the definition of continuity. There's a bit of a trouble with writing the same relations for a general point of discontinuity just because it's difficult to describe the function in just symbols. That could be done, but it would be most of the work. The actual proof of discontinuity would look essentially like the proof for the one example point. – aschepler Oct 24 '22 at 03:04
  • I think $f(x_1)=(1,0)$ and $f(x_2)=(0,1)$. Also, can you change $f$ to $H_1$ as you have defined. In addition, $||H_1(x_1)-H_1(x_2)||=\sqrt{2}\delta'$. Furthermore, on the LHS of the triangle inequality, no matter what rule (either H_1((1,1))=(1,0) or H_1((1,1))=(0,1)), one of the norms is $\delta'$ and the other one is $\sqrt{1+(1+\delta')^2}$, can you explain why it leads to discontinuity? – Saeed Oct 24 '22 at 03:22
  • why $H_1(x_1)=(1, 0)$ it should be $(1+\delta', 0)$ similarly for $x_2$. – Saeed Oct 24 '22 at 03:36
  • I've made some corrections, including changing $x_1$ and $x_2$ so that the function values depend less on $\delta'$. But even for the original $x_1=(1+\delta',1), x_2=(1,1+\delta')$, note $|H_1(x_1)-H_1(x_2)|=\sqrt{2}(1+\delta')$, not $\sqrt{2}\delta'$. And for the last question, $\sqrt{1+(1+\delta')^2}>\sqrt{2}>\epsilon$. Using the triangle inequality shows that not only do those two choices fail, but also any other rule like "split the difference" $H_1((1,1))=\left(\frac 12, \frac 12\right)$. – aschepler Oct 24 '22 at 03:55
  • You still have $f$. Also, what is the value you assume for $H_1((1,1))$. Please clarify that. It should be $(1,0)$ or $(0,1)$. Then one of the norms becomes zero and you cannot violate the inequality. – Saeed Oct 24 '22 at 04:09
  • I do not assume any value for $H_1((1,1))$. That's my point: no possible value can satisfy the inequality. – aschepler Oct 24 '22 at 07:45