How to deal with a sparse matrix when using a perceptron based recommender system?
Recoding the NAs to 0's is not what you want. Think of what this means: a missing value on an item for a particular user means that said user hasn't seen or listened to or bought (depending on what kind of data you have) that item, while a zero value means that the user disliked that item; so they have completely different meanings.

The goal of a recommender system is basically to fill those NA values in a way that "makes sense". It is very common to have sparse matrices in recommender systems. I don't know exactly what kind of approach you're using or why you're using a perceptron, but I would recommend you to check how matrix factorization for recommender systems works ("Matrix factorization for recommender systems" by Robert Bell, Chris Volinsky and Yehuda Koren is a good paper) and see if this approach works for your problem.

You can also try first a simple baseline model that takes into account the biases of the users and the biases of the items; Bell, Volinsky and Koren's paper is a good start.