Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

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.