Michael Lindenbaum, Shai Ben-David
We analyze the amount of information needed to carry out model-based recognition tasks, in the context of a probabilistic data collection model, and independently of the recognition method employed. We consider the very rich class of semi-algebraic 3D objects, and derive an upper bound on the number of data features that (provably) suffice for localizing the object with some pre-specified precision. Our bound is based on analysing the combinatorial complexity of the hypotheses class that one has to choose from, and quantifying it using a VC-dimension parameter. Once this parameter is found, the bounds are obtained by drawing relations between recognition and learning, and using well-known results from computational learning theory. It turns out that this bounds grow logarithmically in the algebraic complexity of the objects.