2
$\begingroup$

What is the Lp norm of the $N$-dimensional Hadamard matrix $H = ((-1)^{i \cdot j})_{i,j}$ for $p > 2$? I know that $\|H\|_1 = N$, $\|H\|_2 = \sqrt{N}$, $\|H\|_\infty = N$ but I can't figure out what it is for other values of $p$. Can we at least give a good upper-bound on it?

Here I consider the induced norm: $\|H\|_p = \max_{x : \|x\|_p = 1} \|Hx\|_p$

(a previous version of this question incorrectly said that $\|H\|_\infty = 1$)

$\endgroup$
6
  • 2
    $\begingroup$ Isn't $\|H\|_\infty = N$ (maximal row sum of absolute values)? $\endgroup$
    – J.J. Green
    Commented Sep 17, 2021 at 0:16
  • $\begingroup$ I've updated my question with a definition of the Lp norm. $\endgroup$ Commented Sep 17, 2021 at 23:26
  • $\begingroup$ Is that a Hadamard matrix? It doesn’t seem like it. $\endgroup$ Commented Sep 18, 2021 at 1:01
  • 1
    $\begingroup$ $i\cdot j$ stands for the inner product of the representation of integers $i,j$ I believe, @ZachTeitler $\endgroup$
    – kodlu
    Commented Sep 18, 2021 at 6:43
  • 2
    $\begingroup$ I agree with @J.J.Green that the question contains an incorrect statement: since the Hadamard matrix is real-symmetric, by duality we have $\Vert H \Vert_p = \Vert H \Vert_q$ when $p$ and $q$ are conjugate indices. Could you please update the question? $\endgroup$
    – Yemon Choi
    Commented Oct 4, 2021 at 18:34

2 Answers 2

8
$\begingroup$

Important Edit: As J.J Green pointed out, the OP contains an incorrectly stated value for $\|H\|_{\infty}$, which I copied without checking below. Interpolating between $(1,\infty)$ using the corrected version would give the trivial bound $\|H\|_p \leq N$. You regain the sharp bound by interpolating instead between $(1,2)$ and $(2,\infty)$.


I assume $L^p$ norm means the operator norm on $\mathbb{R}^N$ with the $\ell_p$ norm.

Then by Riesz-Thorin-Stein interpolation, you have $$ \|H\|_p \leq \|H\|_1^{1/p} \|H\|_\infty^{1-1/p} = \sqrt[p]{N} $$ By testing on the vector $(1,0,0,\ldots,0) \mapsto (-1,1,-1,1,\ldots)$ you have $$ \|H\|_p \geq \sqrt[p]{N} $$

and hence $\sqrt[p]{N}$ is the value.

$\endgroup$
3
  • $\begingroup$ See JJ Green's comment above and answer below. $\endgroup$
    – Yemon Choi
    Commented Oct 4, 2021 at 18:36
  • 1
    $\begingroup$ Oops... in my defense, I assumed that the OP correctly calculated the $\ell_1$ and $\ell_\infty$ operator norms in his question (I took the values from those and didn't double check). $\endgroup$ Commented Oct 4, 2021 at 19:20
  • $\begingroup$ De nada. Question now corrected, it seems. $\endgroup$
    – Yemon Choi
    Commented Oct 5, 2021 at 10:19
5
$\begingroup$

I'm reluctant to contradict Professor Wong, but I think the accepted answer is incorrect since it takes $\left\|H\right\|_\infty$ as 1, whereas it is in fact $N$. But the same argument applies, with Riesz in this case being $$ \left\| H \right\|_p \leq \left\| H \right\|^{2/p}_2 \left\| H \right\|^{1-2/p}_\infty = N^{1/p} N^{1 - 2/p} = N^{1 - 1/p} = N^{1/q} $$ with $q$ the conjugate index to $p$. This inequality is realised by a vector with equal non-zero entries and so gives the equality.

One can confirm this using software such as Matlab or Octave which implement Higham's approximation for $L^p$ norms of matrices for non-trivial $p$, and that gives a lower bound:

octave:1> format long
octave:2> norm(hadamard(2), 4)
ans =  1.68179283050743
octave:3> norm(hadamard(4), 4)
ans =  2.82842712474619
octave:4> norm(hadamard(8), 4)
ans =  4.75682846001088
$\endgroup$
5
  • 1
    $\begingroup$ You are right! (In my defense, I took $\|H\|_{\infty}$ from the OP's question without checking whether it was correctly computed.) $\endgroup$ Commented Oct 4, 2021 at 19:21
  • $\begingroup$ Incidentally, I am curious how Octave computes the matrix norms. Do you have a link to what Higham's approximation does? (I tried Googling, but not being an expert cannot really find it among the other results about approximation and algorithms linked to that name.) $\endgroup$ Commented Oct 5, 2021 at 13:00
  • 1
    $\begingroup$ A variant power-method which is I believe equivalent to a local optimisation (hence always a lower bound on the value), details here: link.springer.com/article/10.1007/BF01396242 $\endgroup$
    – J.J. Green
    Commented Oct 5, 2021 at 13:17
  • $\begingroup$ Thanks; that's pretty neat. $\endgroup$ Commented Oct 5, 2021 at 13:47
  • 1
    $\begingroup$ There is a method (by Stephen Drury) which gets the $\ell_p \rightarrow \ell_q$ operator norm of a matrix to arbitrary accurately using a global subdivide-and-reject method, but is exponential in matrix size so $10 \times 10$ is about as far as you can go: His implementation is here: math.mcgill.ca/drury/research/matsaev/matsaev.html and I made a stab at the same algorithm in C soliton.vm.bytemark.co.uk/pub/jjg/en/code/steckin $\endgroup$
    – J.J. Green
    Commented Oct 5, 2021 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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