[math-fun] Approximate matrix factorization question
Say I've got a mxn matrix that I'd like to factor into an mxk and a kxn matrix. The factorization doesn't have to be exact; I'd just like to minimize some measure of error. What are your favorite algorithms to do this? What assumptions about the matrix and the error measure do they make? There's one blurb in Wikipedia about some nonnegative matrix factorization algorithms: There are several ways in which the W and H may be found: Lee and Seung's multiplicative update rule [10] has been a popular method due to the simplicity of implementation. Since then, a few other algorithmic approaches have been developed. Some successful algorithms are based on alternating non-negative least squares: in each step of such an algorithm, first H is fixed and W found by a non-negative least squares solver, then W is fixed and H is found analogously. The procedures used to solve for W and H may be the same[22] or different, as some NMF variants regularize one of W and H.[17] Specific approaches include the projected gradient descent methods,[22][23]the active set method,[4][24] and the block principal pivoting method[25] among several others. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
It might be worth mentioning that given any way to do this factoring, say M = A x B , then for any kxk matrix G having an inverse H we also have M = (AxG) x (HxB) Also, which ways to find an approximate factorization are best will probably depend on what kind of measure of error is used. If the error used is what is perhaps the most obvious one, namely Err(M; A, B) = L_2(M - AxB) where L_2(N) is defined as the sum of the squared entries of N (or sum of squared absolute values if over the complexes), then probably just a garden-variety optimization algorithm will work well. (E.g., a conjugate-gradient method from "Practical Optimization" by Murray, Gill, and Wright — a book I highly recommend.) —Dan
On Feb 24, 2016, at 10:43 AM, Mike Stay <metaweta@gmail.com> wrote:
Say I've got a mxn matrix that I'd like to factor into an mxk and a kxn matrix. The factorization doesn't have to be exact; I'd just like to minimize some measure of error.
What are your favorite algorithms to do this? What assumptions about the matrix and the error measure do they make?
There's one blurb in Wikipedia about some nonnegative matrix factorization algorithms:
There are several ways in which the W and H may be found: Lee and Seung's multiplicative update rule [10] has been a popular method due to the simplicity of implementation. Since then, a few other algorithmic approaches have been developed.
Some successful algorithms are based on alternating non-negative least squares: in each step of such an algorithm, first H is fixed and W found by a non-negative least squares solver, then W is fixed and H is found analogously. The procedures used to solve for W and H may be the same[22] or different, as some NMF variants regularize one of W and H.[17] Specific approaches include the projected gradient descent methods,[22][23]the active set method,[4][24] and the block principal pivoting method[25] among several others.
On Feb 24, 2016, at 2:13 PM, Dan Asimov <dasimov@earthlink.net> wrote:
It might be worth mentioning that given any way to do this factoring, say
M = A x B
, then for any kxk matrix G having an inverse H we also have
M = (AxG) x (HxB)
This runs into problems when you want to keep the factors non-negative, which was Mike’s question. Fun puzzle: what group of matrices (for insertion) preserves non-negativity?
Also, which ways to find an approximate factorization are best will probably depend on what kind of measure of error is used.
If the error used is what is perhaps the most obvious one, namely
Err(M; A, B) = L_2(M - AxB)
where L_2(N) is defined as the sum of the squared entries of N (or sum of squared absolute values if over the complexes), then probably just a garden-variety optimization algorithm will work well.
(E.g., a conjugate-gradient method from "Practical Optimization" by Murray, Gill, and Wright — a book I highly recommend.)
—Dan
To be clear: nonnegativity isn't required; it was just one example of an assumption made about the matrix in those algorithms. On Wed, Feb 24, 2016 at 11:50 AM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 24, 2016, at 2:13 PM, Dan Asimov <dasimov@earthlink.net> wrote:
It might be worth mentioning that given any way to do this factoring, say
M = A x B
, then for any kxk matrix G having an inverse H we also have
M = (AxG) x (HxB)
This runs into problems when you want to keep the factors non-negative, which was Mike’s question. Fun puzzle: what group of matrices (for insertion) preserves non-negativity?
Also, which ways to find an approximate factorization are best will probably depend on what kind of measure of error is used.
If the error used is what is perhaps the most obvious one, namely
Err(M; A, B) = L_2(M - AxB)
where L_2(N) is defined as the sum of the squared entries of N (or sum of squared absolute values if over the complexes), then probably just a garden-variety optimization algorithm will work well.
(E.g., a conjugate-gradient method from "Practical Optimization" by Murray, Gill, and Wright — a book I highly recommend.)
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
Would lower triangular square matrices (i.e., including the diagonal) with positive entries work? —Dan
On Feb 24, 2016, at 11:50 AM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 24, 2016, at 2:13 PM, Dan Asimov <dasimov@earthlink.net <mailto:dasimov@earthlink.net>> wrote:
[If]
M = A x B
, then for any kxk matrix G having an inverse H we also have
M = (AxG) x (HxB)
. . . Fun puzzle: what group of matrices (for insertion) preserves non-negativity?
Never mind, I doubt the posistive triangular matrices is closed under inverses. But: Certainly the group of positive diagonal matrices would work. Anything else? —Dan
On Feb 24, 2016, at 12:27 PM, Dan Asimov <asimov@msri.org> wrote:
Would lower triangular square matrices (i.e., including the diagonal) with positive entries work?
—Dan
On Feb 24, 2016, at 11:50 AM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 24, 2016, at 2:13 PM, Dan Asimov <dasimov@earthlink.net <mailto:dasimov@earthlink.net>> wrote:
[If]
M = A x B
, then for any kxk matrix G having an inverse H we also have
M = (AxG) x (HxB)
. . . Fun puzzle: what group of matrices (for insertion) preserves non-negativity?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Feb 24, 2016, at 3:36 PM, Dan Asimov <asimov@msri.org> wrote:
Never mind, I doubt the posistive triangular matrices is closed under inverses.
But: Certainly the group of positive diagonal matrices would work. Anything else?
Yes. Here’s a hint: Instead of thinking about the group of matrices, think about the corresponding group of transformations of the positive orthant.
—Dan
Aha, so maybe the largest such group is the group of matrices that permute, and multiply by a positive number, each basis element. Thus, the group of matrices with all 0's except for a single positive number in each row and in each column? —Dan
On Feb 24, 2016, at 12:48 PM, Veit Elser <ve10@cornell.edu> wrote:
On Feb 24, 2016, at 3:36 PM, Dan Asimov <asimov@msri.org> wrote:
Never mind, I doubt the posistive triangular matrices is closed under inverses.
But: Certainly the group of positive diagonal matrices would work. Anything else?
Yes. Here’s a hint:
Instead of thinking about the group of matrices, think about the corresponding group of transformations of the positive orthant.
That’s it.
On Feb 24, 2016, at 3:59 PM, Dan Asimov <asimov@msri.org> wrote:
Aha, so maybe the largest such group is the group of matrices that permute, and multiply by a positive number, each basis element.
Thus, the group of matrices with all 0's except for a single positive number in each row and in each column?
—Dan
On Wed, 24 Feb 2016, Mike Stay wrote:
Say I've got a mxn matrix that I'd like to factor into an mxk and a kxn matrix. The factorization doesn't have to be exact; I'd just like to minimize some measure of error.
What are your favorite algorithms to do this? What assumptions about the matrix and the error measure do they make?
The usual way to do this is to take the singular value decomposition (SVD) and discard all but a few of the largest singular values (and the corresponding left and right singular vectors). This is the essence of "principal components analysis" (PCA). Makes no assumptions about the matrix. I'm not an expert, so I can't say what error measure this corresponds to. There's an enormous literature on PCA. Wikipedia appears to be very good on the subject. -- Tom Duff. In argento plane studiosus sum.
participants (5)
-
Dan Asimov -
Dan Asimov -
Mike Stay -
Tom Duff -
Veit Elser