Skip to main content
2 of 7
removed the functional-analysis tag
leo monsaingeon
  • 5.4k
  • 2
  • 23
  • 45

Bounds on $sgn(Au) - sgn(Av)$ when $||u-v||_1 \leq \epsilon$

Suppose A is a $n \times n$ Hermitian and Unitary matrix. i.e. $A^{\dagger}=A$ and $A^{\dagger}A=I =AA^{\dagger}$. (Assume all entries are real)

And let $u \in \{-1,1\}^n$, $v \in \{-1,1\}^n$.

Suppose $||u- v||_1 \leq \epsilon N$. (i.e. $u$ and $v$ differ on $\epsilon N$ coordinates)

and $sgn: \mathbb{R} \rightarrow \{-1,0,1\}$ be the sign function, i.e. maps all negative numbers to $-1$, and positive numbers to $1$, and $0$ to $0$.

I want a non-trivial upper bound on $$||sgn(Au)-sgn(Av)||_1$$ in terms of $\epsilon$. For example, is it upper bounded by $4\epsilon N$?

Subhayan
  • 221
  • 1
  • 4