wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> about matrix approximation
        
(Message started by: cuckoo on Apr 5^th, 2009, 9:07am)

Title: about matrix approximation
Post by cuckoo on Apr 5^th, 2009, 9:07am

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.

Title: Re: about matrix approximation
Post by william wu on Aug 9^th, 2010, 12:00pm

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.