Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a real matrix $A$ find a positive vector $x$ of unit length ($x^T x = 1$) for which $x^T A^T A x$ is minimal (closest to $0$).

A has size about $1000 \times 20$ and can be written as $[ A_P | A_N ]$ ($A_P$ contains only positive and $A_N$ only negative numbers)

Is there any deterministic algorithm which can reach the solution (global minimum) in polynomial time?

share|cite|improve this question
Isn't this a least squares problem? Weighted_least_squares – nbubis Apr 10 '12 at 11:59
I think the problem is in the constraint. Without the constraint $x^Tx = 1$, there is trivial solution $x=0$ – Boris Apr 10 '12 at 14:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.