wu :: forums « wu :: forums - about matrix approximation » Welcome, Guest. Please Login or Register. Mar 3rd, 2024, 11:06pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Icarus, william wu, Grimbal, Eigenray, towr, SMQ)    about matrix approximation « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
cuckoo
Junior Member

Gender:
Posts: 57
 about matrix approximation   « on: Apr 5th, 2009, 9:07am » Quote Modify

SVD solves the matrix approximation problem under Frobenius norm.
What if the matrix norm is defined as maximizing number of zero elements? More specifically, given a matrix A, and a specified rank r (r<rank(A)). Find a matix B such that rank(B)=r and B maxizes the number of zero elements in A-B.
 « Last Edit: Apr 5th, 2009, 9:11am by cuckoo » IP Logged
william wu

Gender:
Posts: 1291
 Re: about matrix approximation   « Reply #1 on: Aug 9th, 2010, 12:00pm » Quote Modify

Suppose the matrices are m by n.

Is it correct to say that no generality is lost in assuming that B_ij = 0 or B_ij = A_ij?

In which case, we could brute-force through all 2^(mn) possible matrices for B, and pick the one such that the number of zeros in A - B is maximized, and rank(B) = r. The only concern is whether or not we can find B such that rank(B) = r under the above assumption.

 IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »