ABSTRACT
Making digital representations of physical objects has been approached with a pessimistic attitude demanding a very high rate of regularly-spaced measurements without taking into account that the object itself might have sparsity. In this text sparsity is used as an operational gauge of an object’s complexity rather than a well-defined mathematical property. In mathematics we define a sparse matrix in contrast to a dense one as containing mostly zeroes. Compressed sampling takes into account the sparsity of an object and is able to successfully reconstruct images even after dramatically reducing the number of measurements required without loss of reconstruction fidelity. If one defines “sampling” as the act of performing measurements of different objects such as pixels in an image, one can conservatively measure one at a time or group several objects and measure groupings. Compressed sensing allows us to optimize measurements of such groupings and thereby perform significantly fewer measurements. This is related to the 12-ball problem, where one is tasked with finding one lighter or heavier ball out of a set of 12 balls by only three comparative weighing of groupings.1
