wu :: forums « wu :: forums - about matrix approximation » Welcome, Guest. Please Login or Register. Mar 21st, 2023, 7:06pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register wu :: forums  riddles  putnam exam (pure math) (Moderators: towr, Icarus, william wu, SMQ, Eigenray, Grimbal)  about matrix approximation « Previous topic | Next topic » Author Topic: about matrix approximation  (Read 7906 times)
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

 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 »