wu :: forums
wu :: forums - about matrix approximation

Welcome, Guest. Please Login or Register.
Sep 30th, 2022, 2:30pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: SMQ, Icarus, Eigenray, william wu, Grimbal, towr)
   about matrix approximation
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: about matrix approximation  (Read 7901 times)
cuckoo
Junior Member
**





   


Gender: male
Posts: 57
about matrix approximation  
« on: Apr 5th, 2009, 9:07am »
Quote Quote Modify 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
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: about matrix approximation  
« Reply #1 on: Aug 9th, 2010, 12:00pm »
Quote Quote Modify 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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board