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$)

Improve this question
$\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$
    – permanganate
    Commented Sep 17, 2021 at 23:26
  • $\begingroup$ Is that a Hadamard matrix? It doesn’t seem like it. $\endgroup$
    – Zach Teitler
    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

Reset to default
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.

Improve this answer
$\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$
    – Willie Wong
    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
Improve this answer
$\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$
    – Willie Wong
    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$
    – Willie Wong
    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$
    – Willie Wong
    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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .