2
$\begingroup$

Let $\mathbf{A}$ be any $n\times n$ symmetric positive matrix ($A_{ij}>0$). It is easy to show that the solution to the following optimization problem

\begin{align} \max_{\mathbf{x}}~~\mathbf{x^TAx}\,\,;s.t.~~\mathbf{x}\geq \mathbf{0},~~\|\mathbf{x}\|_2=1 \end{align}

is given by the so-called Perron vector of $\mathbf{A}$, which will the eigenvector corresponding to the largest eigenvalue (known as the Perron root). It will also turn out that the Perron vector has all its entries as positive. I need to see if Perron vector is still a solution if I replace the $2$-norm constraint with the $1$-norm constraint. I need to know if the Perron vector will be a solution to

\begin{align} \max_{\mathbf{x}}~~\mathbf{x^TAx}\,\,;s.t.~~\mathbf{x}\geq \mathbf{0},~~\|\mathbf{x}\|_1=1 \end{align}

If it is not, how badly does it miss out? Is there any research on this? This comes from an engineering problem I am working on.

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ In English, in such names as "Perron vector", the capital letter is used. $\endgroup$
    – Alexandre Eremenko
    Commented Sep 17, 2019 at 12:12
  • $\begingroup$ Just consider the identity matrix. Every feasible vector (feasible means satisfies the constraints) is also optimal for the first problem but it may not even be feasible for the second one. $\endgroup$
    – Pushpendre
    Commented Sep 18, 2019 at 2:30
  • $\begingroup$ @Pushpendre thanks!. In my case, the matrix is strictly positive ($A_{ij}>0$) and in fact, it is ok to assume that the matrix is positive definite. Examples pointed out in the answer as well as your comment are extremely sparse. I am wondering (and hoping) if that makes a difference $\endgroup$
    – dineshdileep
    Commented Sep 18, 2019 at 3:07
  • $\begingroup$ Why is this convex? $\endgroup$
    – Rodrigo de Azevedo
    Commented Sep 18, 2019 at 6:00
  • $\begingroup$ It doesn't require convexity. $\endgroup$
    – dineshdileep
    Commented Sep 18, 2019 at 6:04

1 Answer 1

Reset to default
7
$\begingroup$

No. The Perron vector is in general very far from optimizing the quantity you're looking at. Here is an example: Let $A$ be the $n\times n$ tridiagonal matrix with $\frac 13$ on the diagonal and the off-diagonals as well as in the $(1,n)$ and $(n,1)$ entries. (I think of this as a Markov transition matrix on a ring of size $n$ with probability $\frac 13$ of staying still or moving left or right).

The Perron vector of norm 1 is the vector $x=(\frac 1n,\ldots,\frac 1n)^T$. This is an eigenvector with eigenvalue 1, so that $x^TAx=1/n$. On the other hand, if $y$ is the coordinate vector $(1,0,\ldots,0)^T$, then $y^TAy=\frac 13$ so the Perron vector is nowhere close to optimizing $x^TAx$ over the $\ell^1$ unit ball.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, this is insightful. But please note that the matrix I have is strictly positive ($A_{ij}>0$) whereas the matrix in your example is extremely sparse for larger $n$. Do you think this will make a difference? $\endgroup$
    – dineshdileep
    Commented Sep 17, 2019 at 3:47
  • 1
    $\begingroup$ @dineshdileep: No, this doesn't make a difference. You can simply perturb the matrix to make all entries strictly positive, but if the perturbation is small enough, this won't change the phenomenon described in Anthony Quas' answer. $\endgroup$
    – Jochen Glueck
    Commented Sep 17, 2019 at 6:26
  • 2
    $\begingroup$ The spirit of the answer is that $\ell^2$ looks very different from $\ell^1$ in the diagonal direction (by a factor of $\sqrt n$). Finding a matrix whose Perron vector is close to the diagonal direction means that the $\ell^1$ version of it is much smaller. This makes it easier to beat the value coming from the Perron vector. As an explicit perturbation along the lines suggested by @JochenGlueck, you could replace all of the 1/3 by 1/4; and replace the 0’s by $1/(4(n-3))$. The Perron vector is the same so $x^TAx=1/n$ and $y^TAy=1/4$. $\endgroup$
    – Anthony Quas
    Commented Sep 17, 2019 at 23:36
  • $\begingroup$ @AnthonyQuas got it!... $\endgroup$
    – dineshdileep
    Commented Sep 18, 2019 at 3:08

You must log in to answer this question.

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