Method and apparatus for compressed sensing yields acceptable quality reconstructions of an object from reduced numbers of measurements. A component x of a signal or image is represented as a vector having m entries. Measurements y, comprising a vector with n entries, where n is less than m, are made. An approximate reconstruction of the m-vector x is made from y. Special measurement matrices allow measurements y=Ax+z, where y is the measured m-vector, x the desired n-vector and z an m-vector representing noise. "A" is an n by m matrix, i.e. an array with fewer rows than columns. "A" enables delivery of an approximate reconstruction, x.sup.#, of x. An embodiment discloses approximate reconstruction of x from the reduced-dimensionality measurement y. Given y, and the matrix A, x.sup.# of x is possible. This embodiment is driven by the goal of promoting the approximate sparsity of x.sup.#.