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

Question

$\DeclareMathOperator\sgn{sgn}$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 $\frac{\epsilon}{2} 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$?

Answer 1

There is a straightforward bound.

Consider A to be the $\log(N)$-fold tensor product of $H= \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$.

A is Unitary and Hermitian. In fact A is just the Fourier transform.

Set $u$ to be all one vector, i.e. $u=(1, 1, 1, \ldots , 1)^T$.

And $v$ is all one vector with the first coordinate set to $-1$, i.e. $v=(-1, 1, 1, \ldots , 1)^T$

See $Au =(1, 0 , 0 , \ldots 0)^T$

and $Av$ has non zero entries in all coordinates.

Thus, $\|\operatorname{sgn}(Au)-\operatorname{sgn}(Av)\|_1 \geq N-1$.

Conclusion. No non-trivial bound.