6
$\begingroup$

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 ! :)

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Nathaniel Johnston
    Commented Mar 19, 2021 at 12:35
  • 1
    $\begingroup$ 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? $\endgroup$
    – Seva
    Commented Mar 19, 2021 at 14:23
  • $\begingroup$ 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. $\endgroup$
    – PAb
    Commented Mar 19, 2021 at 14:26
  • $\begingroup$ I am interested in any regime, but the most interesting would be n, m $\rightarrow + \infty$ with n / m a constant. $\endgroup$
    – PAb
    Commented Mar 19, 2021 at 14:27
  • $\begingroup$ @PAb - You're right -- ignore my comment about the minimum equaling $1$. $\endgroup$
    – Nathaniel Johnston
    Commented Mar 19, 2021 at 14:52

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Nice. The argument in my answer is precisely the justification of your last sentence. $\endgroup$
    – Mikael de la Salle
    Commented Mar 19, 2021 at 16:35
3
$\begingroup$

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}}$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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