5
$\begingroup$

This is a problem that I encountered during my research, and I have spent a good amount of time on it without success. So I am reaching out for help .... Any pointers or suggestions are appreicated!

The problem: Let $m\geq8$ be an even integer and $\varepsilon,\alpha\in\left( 0,1\right) $ be two fixed constants. For each $m$ large enough, construct or an orthogonal matrix $\mathbf{T}_{m}=\left( \gamma_{ij}\right) $ such that

  1. Each $\gamma_{ij} \neq 0$ for $1 \leq i \leq j \leq m$;

  2. The following inequality holds $$ 1 -\varepsilon \geq \min_{\left[ \alpha m\right] +1\leq i\leq m}\sum_{j=\left[ \alpha m\right] +1}^{m}\gamma_{ij}^{2}\geq\varepsilon, $$ where $\left[ x\right] $ denotes the integer part of $x\in\mathbb{R}$.

    1. Put the last $m-[\alpha m]$ columns (by keeping the order of the column indices) of $\mathbf{T}_{m}$ into a matrix $\mathbf{R}$. Then, for the matrix $\mathbf{R}$ and a constant $\beta \in (0,\alpha)$, pick a submatrix $\mathbf{G}$ of size $[\beta m] \times (m-[\alpha m])$ from the first $[\alpha m]$ rows of $\mathbf{R}$. Also pick a submatrix of $\mathbf{H}$ of size $[\beta m] \times (m-[\alpha m])$ from the last $m-[\alpha m]$ rows of $\mathbf{R}$. Then, no such $\beta$ exists such that $\mathbf{G} = - \mathbf{H}$ or $\mathbf{G} = \mathbf{H}$ for any $\mathbf{G}$ and $\mathbf{H}$ thus picked.

The inequality in display requires that the lower right block of size $[\left( 1-\alpha\right) m]$ of $\mathbf{T}_{m}$ has rows of Euclidean norms bounded from below by $\varepsilon$ and from above by $1 -\varepsilon$ regardless of what $m$ is. It becomes highly nontrivial to obtain such a $\mathbf{T}_{m}$.

Constructive proof for such a sequence $\left\{ \mathbf{T}_{m}\right\} _{m\geq8,m\in2\mathbb{N}}$ is preferred.

Note I edited the problem. Now a third restriction is added. Without the third restriction, Walsh matrices pointed by Dr. Bill Johnson satisfy the rest two.

Background I encountered this problem when I was trying to contruct a counterexample to a general claim made in a published paper on the convergence of a stochastic process related to high-dimensional multiple testing.

My attempts The simple reflection trick to construct an orthogonal matrix is not able to obtain $\mathbf{T}_m$ for which the displayed inequality holds. I also tried (a) using the Haar measure to show the existence of such an $\mathbf{T}_m$ with positive probability but it essentially reduces to the same problem described above; (b) tried orthogonal matrix induced by dicrete cosine transform, but it can not achieve the uniformity needed in the displayed inequality.

Improve this question
$\endgroup$
6
  • $\begingroup$ Use Walsh matrices. $\endgroup$
    – Bill Johnson
    Commented Dec 6, 2015 at 19:14
  • $\begingroup$ @Stefan Kohl: how to add a top-level tag?@Bill Johnson: I see; only need to normalize the Walsh matrices. Thank you both! $\endgroup$
    – Chee
    Commented Dec 6, 2015 at 19:59
  • $\begingroup$ Probably you don't mean what you wrote down as a formula (your verbal description doesn't match this either). To get the minimum between the required bounds, just take a lower right block that is diagonal, with all $1$'s, except for one $\sqrt{\epsilon}$, and now it's trivial to build a unitary matrix out of this (it can be diagonal except for two non-diagonal entries). $\endgroup$
    – Christian Remling
    Commented Dec 6, 2015 at 21:19
  • $\begingroup$ @ChristianRemling: sharp eyes! After I posted the orignal problem, where it was also required that $\gamma_{ij} \neq 0$ for each $i,j$, I removed this requirement since I thought it may be hard to find such an orthogonal matrix for each such $m$. Then Dr. Johnson pionted out the Walsh matrices, which satisfy both two requirements. Now that I have read your comments, and I added this requirement back. $\endgroup$
    – Chee
    Commented Dec 7, 2015 at 1:04
  • $\begingroup$ @Chee: I don't think requiring $\gamma_{ij}\not= 0$ changes much, I'm pretty confident a small perturbation (within $O(m)$) of my example (say) will have this property generically. $\endgroup$
    – Christian Remling
    Commented Dec 7, 2015 at 20:17

0

Reset to default

You must log in to answer this question.