View Single Post
Old 07-11-2012, 02:03 AM
htlin's Avatar
htlin htlin is offline
Join Date: Aug 2009
Location: Taipei, Taiwan
Posts: 601
Default Re: How to calculate VC dimension for matrix factorization (Netflix-like) tasks

Assume that the input space to be all the entries in the M by N (binary) matrix, and each hypothesis is simply sign(P * Q) for two matrices of rank at most K. The following paper

gives a combinatorial upper bound on the growth function, and thus the VC dimension is bounded by K(M+N)* some log factors. Hope this helps.
When one teaches, two learn.
Reply With Quote