The invention provides a method and apparatus for making reduced numbers of measurements compared to
current practice and still give acceptable quality reconstructions of the object of interest. In one embodiment, a
digital signal or image is approximated using significantly fewer measurements than with traditional measurement schemes. A component x of the
signal or image can be represented as a vector with m entries; traditional approaches would make m measurements to determine the m entries. The disclosed technique makes measurements y comprising a vector with only n entries, where n is less than m. From these n measurements, the disclosed invention delivers an approximate reconstruction of the m-vector x. In another embodiment, special measurement matrices called CS-matrices are designed for use in connection with the embodiment described above. Such measurement matrices are designed for use in settings where sensors can allow measurements y which can be represented as y=Ax+z, with y the measured m-vector, x the desired n-vector and z an m-vector representing
noise. Here, A is an n by m matrix, i.e. an array with fewer rows than columns. A technique is disclosed to design matrices A which support delivery of an approximate reconstruction of the m-vector x, described above. Another embodiment of the invention discloses approximate reconstruction of the vector x from the reduced-dimensionality measurement y within the context of the embodiment described above. Given the measurements y, and the CS matrix A, the invention delivers an approximate reconstruction x# of the desired
signal x. This embodiment is driven by the goal of promoting the approximate sparsity of x#.