Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 3 down vote favorite

I am looking for an efficient method to compute $$\sum_{i=1}^\left|B\right|\left|Ax_i-b_i\right|^2\rightarrow min$$ under the condition $$\forall i, x_i\ge 0,$$ where $A$ is an n-by-m matrix and $B$ is a set of n-dimensional vectors. Only $B$, $n$ and $m$ are given. In other words the goal is to find $A$ so that the sum of squares of the orthogonal distance of the subspace defined by the columns of $A$ (under the non-negativity constraint) to every point in $B$ is minimal. $B$ is a finite set with approximately 10 to 1000 elements and $n$ is in the range of 50 to 1000 and $m$ will be rather small, i.e. $\le 10$.

share|improve this question

2 Answers

up vote 3 down vote accepted

EDIT: Rewritten after clearing up some notational confusion in the comments.

Let $X = \left[x_1, x_2, \ldots x_r\right]$ and $B = \left[b_1, b_2, \ldots b_r\right]$ where $r$ is the numbers of vectors. Your problem can then be written as

$$ \text{minimize}_{A,X\geq 0} ||AX-B||$$

This looks very much like a version of the non-negative matrix factorization problem, and is called semi-nonnegative matrix factorization. See here for an example.

share|improve this answer
Yes, the goal is to find an $A$ where where the sum of all $\left|Ax_i=b\right|^2$ (many different $b$ and $x_i$) is minimal. I don't see how I could reduce $Ax$ to $v$ or am I missing something. – simmmons Aug 8 '12 at 8:14
Is $x$ given or do you want to find it too, or how does $x$ enter the game. Your notation is a bit confusing regarding $x$. In your new notation, is $x_i$ a vector or a scalar, and should it be $b_i$? – Johan Löfberg Aug 8 '12 at 8:54
Yes, it is supposed to be $b_i$. $x$ is not given but has a minor role, meaning the actual values are not of interest. The whole problem is similar to a principle component analysis but with the constraint of x being non-negative and that the components (i.e. column vectors in A) do not have to be orthogonal. To summarise, the goal is to find an $m$-dimensional subspace, bounded by the non-negativity constraint that minimises the total least squares to a set of points in an $n$-dimensional space, where $m<<n$. – simmmons Aug 8 '12 at 9:02
OK. I don't think you can get away with searching for a specific value of $x$, although it is no interest. Just blindly looking at the problem then, you have a nonlinear least-squares problem (since you have a bilinear product between $A$ and $x$). On the positive side, your problem is a classical one. I will update my answer to reflect this. – Johan Löfberg Aug 8 '12 at 9:15
Thanks a lot. You are right it is very similar to non-negative matrix factorisation (NNMF) but NNMF has an additional constraint of $A\ge0$. How can I solve this problem without this additional constraint? – simmmons Aug 8 '12 at 9:33
show 2 more comments
up vote 3 down vote

You can transform this into a standard form quadratic program by expanding the square term, then distributing the sum (assuming your set B is finite). You can then use one of the standard solvers (see the links at the bottom of the wikipedia page for several options).

If you are looking for more specific advice, I'd suggest adding more detail about your specific problem, including the size of your problem (how big n and m are), and if there is any structure to your matrix A.

share|improve this answer
Thanks for the answer. I added a few sentences to the question detailing the problem and its size. And I think it might not have been clear that the goal is to find an $A$ where the sum of the quadratic distances is minimal. Furthermore, I am unfamiliar with quadratic programming and am not sure how to approach this problem. I would appreciate any further help. – simmmons Aug 8 '12 at 7:34
1  
@simmmons, you've rewritten your question to indicate that $A$ is one of the input variables, which I think invalidates Marc's answer. – Aron Ahmadia Aug 8 '12 at 13:12

Your Answer

 
discard

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

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