6
$\begingroup$

Let $A \in \mathbb{R}^{n \times n}$ be a symmetric matrix with entries $A_{ij} \sim \mathcal{N} (0,1)$, all independent except for the symmetry condition.

Consider the following minimization problem:

\begin{equation} \inf \limits_{u \in \mathbb{R}^n : \sum u_i = 0 }\{ \ \lambda_{max}( A - \text{Diag}(u))\} \end{equation}

where $\lambda_{max}(\cdot)$ denotes the largest eigenvalue and $\text{D}(v)$ is the diagonal matrix having the vector $v \in \mathbb{R}^n$ as entries.

I don't want to necessarily find the optimal value of this problem. It would suffice to find a vector $u$ that achieves a smaller value than the trivial vector $0 \in \mathbb{R}^n$, for large $n$.

Question: How would one find a vector $u$, with $\sum_i u_i = 0 $ (possibly random and dependent on $A$), that achives a smaller value than the zero vector asymptotically for large $n$ with high probability? For the zero vector the value is $\lambda_{max}(A)$ for which it is know that $\lambda_{max}(A) = \Theta( 2 n^{3/2}) $.

Is there existing literature on this problem? What methods might one use?

Improve this question
$\endgroup$
11
  • $\begingroup$ Out of curiosity, why do you want that $\sum u_i = 0$? $\endgroup$
    – smapers
    Feb 5, 2020 at 15:50
  • $\begingroup$ The mentioned problem can be viewed as an upper bound to the problem of maximizing $x^t A x$ over the hypercube. $\endgroup$
    – sigmatau
    Feb 5, 2020 at 15:59
  • $\begingroup$ I would like to find a vector such that the value is smaller than the value attained by the zero vector with high probability for $n \to \infty$. $\endgroup$
    – sigmatau
    Feb 5, 2020 at 16:05
  • $\begingroup$ I think that due to the $\Sigma u_i = 0$ constraint and the convexity of $\lambda_{max}$, Jensen's inequality is going against you. $\endgroup$
    – Mark L. Stone
    Feb 5, 2020 at 16:38
  • 1
    $\begingroup$ @smapers That was not clearly written out. The expectation is (sort of?) conditional on the value of A. I.e., randomly reordering elements of u for a fixed $A$. Anyhow, this is not a rigorous argument, rather, a germ of an idea, and perhaps it is wrong. That is why I did not submit it as an answer. $\endgroup$
    – Mark L. Stone
    Feb 6, 2020 at 13:23

1 Answer 1

Reset to default
0
$\begingroup$

For a given instantiation of $A$, the globally optimal value of $u$ can be found as the solution of a convex Linear Semidefinite Programming (SDP) problem using a standard solver such as Mosek. This optimum achieves a better objective value than $u = 0$ a.s. for $n \ge 2$.

Now assume, I believe as intended, that $u$ must be specified only with knowledge of $n$, but not with knowledge of a specific instantiation of $A$.

By convexity of $\lambda_{max}$ of a real symmetric matrix, $$\lambda_{max}(A) \le \frac{1}{2}\lambda_{max}(A-\text{diag}(u)) + \frac{1}{2}\lambda_{max}(A-\text{diag}(-u))$$

Taking expectation of both sides, $$E(\lambda_{max}(A)) \le \frac{1}{2}E(\lambda_{max}(A-\text{diag}(u))) + \frac{1}{2}E(\lambda_{max}(A-\text{diag}(-u)))$$

Because $u$ was chosen without knowledge of the instantiation of $A$, and all elements of $A$ are symmetrically distributed about zero, it must be the case that $$E(\lambda_{max}(A-\text{diag}(-u))) =E(\lambda_{max}(A-\text{diag}(u)))$$

and therefore $$E(\lambda_{max}(A)) \le E(\lambda_{max}(A-\text{diag}(u)))$$

So such a $u$ can do no better on average than $u = 0$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Does the downvoter care to explain the downvote? $\endgroup$
    – Mark L. Stone
    Apr 21, 2020 at 1:46

Your Answer

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

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