5

I am trying to get a lower bound (or even the exact value) of

$$ \min_{X \in \mathbb{R}^{n\times n}} \|X - I_n\|_{\infty} \enspace \text{s.t.} \enspace \mbox{Rank}(X) = m $$

where $m \leq n$, and the infinity norm is

$$ \| X \|_{\infty} := \max_{ij}|X_{ij}| $$

I have a very simple lower bound, obtained with norm equivalence:

$$\|X - I_n\|_{\infty} \geq \frac{1}{n} \|X - I_n\|_F\geq \frac{\sqrt{n - m}}{n}$$

but this is obviously not tight, and experiments suggest that the scaling is wrong.

Thanks a lot ! :)

Rodrigo de Azevedo
  • 1
PAb
  • 187
  • 3
    Is the infinity norm the induced infinity norm? Or the Schatten infinity norm (i.e., operator/spectral norm)? For the induced norm, I'm pretty sure the minimum equals $1$ for all $m < n$. For the Schatten norm, I think the norm equivalence factor should be $1/\sqrt{n}$, not $1/n$. – Nathaniel Johnston Mar 19 '21 at 12:35
  • 1
    What is the regime you are interested in: $m$ close to $n$, or $m$ small? Do you need a lower or an upper bound for the smallest possible norm? And, seconding the previous comment, what do you mean by the infinity norm? – Seva Mar 19 '21 at 14:23
  • The inifinity norm above is the induced norm: $|X|{\infty} = \max{ij}|X_{ij}|$. I have edited the original post. Do you have an explanation about why this should be one? I think you can easily get 1/2 by using rank one matrices. – PAb Mar 19 '21 at 14:26
  • I am interested in any regime, but the most interesting would be n, m $\rightarrow + \infty$ with n / m a constant. – PAb Mar 19 '21 at 14:27
  • @PAb - You're right -- ignore my comment about the minimum equaling $1$. – Nathaniel Johnston Mar 19 '21 at 14:52
  • You should get precise asymptotics from the answers to https://mathoverflow.net/questions/24864/almost-orthogonal-vectors – Mikael de la Salle Mar 19 '21 at 14:56
  • Relevant: https://arxiv.org/abs/1705.07474 – Dustin G. Mixon Mar 19 '21 at 15:19

2 Answers2

4

Theorem 1.1 from Alon's paper "Perturbed identity matrices have high rank: proof and applications" says that if $\|X-I_n\|_\infty<c$ with $1/(2\sqrt n)<c<1/4$, then $m\gg \log n/(c^2\log(1/c))$ with an absolute implicit constant. This is exactly what you need: if $X$ is close to the identity matrix in the infinity norm, then the rank of $X$ is large. Incidentally, ALon's bound is sharp up to a logarithmic factor; therefore, you cannot expect to get much better estimates.

Seva
  • 22,827
2

Your simple lower bound is not so bad, in particular when $m$ is of order $cn$ for $0<c<1$.

Indeed, it follows from the answers to this question that there are unit vectors $u_1,...,u_n$ in $\mathbf{R}^m$ such that $|\langle u_i,u_j\rangle| \leq C \sqrt{\frac{\log n}{m}}$ for every $i \neq j$. Taking $X = (\langle u_i,u_j\rangle)_{i,j}$ yields that the minimum is at most $C \sqrt{\frac{\log n}{m}}$.

Mikael de la Salle
  • 9,260