$\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$?

  • 1
    $\begingroup$ Since each place where $u$ and $v$ differ contributes 2 to their $\operatorname L^1$-distance, I guess you want $\|u - v\| \le 2\epsilon N$, or that $u$ and $v$ differ in at most $\frac1 2\epsilon N$ places? $\endgroup$ – LSpice May 18 '20 at 23:12
  • $\begingroup$ @Omnomnomnom, thanks for fixing my bone-headed error of including \sgn in the subject. $\endgroup$ – LSpice May 19 '20 at 1:24
  • 1
    $\begingroup$ @LSpice No problem. Anyway, Mathjax doesn't behave in an intuitive way. For instance, despite the fact that your command is only defined in the question body, it used to be the case that the command \sgn would work in any answer-posts below your definition. $\endgroup$ – Ben Grossmann May 19 '20 at 1:26

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.