We take some cases that may be analyzed on the back of an envelope. We consider here a space I of images where each image is a vector of n reals, each between 0 and 1. I = [0, 1]n. The index set J with n elements is used to select elements (pixels) from one of these images. n is about 220 or much smaller is special cases. If j ∊ J and i ∊ I then “i(j)” denotes the pixel in the image i selected by j.
Since the components of the vectors in I are clamped between 0 and 1, I is not a vector space, but it is a subset of the vector space ℝn. The components of a vector in I are to be interpreted as monochromatic pixel values. (Note that ‘vector’ and ‘image’ mean the same below—the choice is to invoke connotations.)
We have another real vector space S of k dimensions where k is considerably less than n. k may be approximately n¾. S is the vector space of possible records. The technology observes an element i from I, records an element s from S and later tries to approximate i given s. The benefit is that the record is smaller to store and quicker to sense and transmit. s = Φi where Φ is some known fixed linear transformation from I to S. We assume in this note that the nk elements of Φ are each either 0 or 1 chosen randomly and independently with probability 1/2. We may speak of a row of Φ as a subset of J. This is presumably feasible using conventional pseudo random generators for Φ. We strive here to understand the nature of this approximation—which approximations are subjectively adequate, and which are technologically feasible. In practice the components of a vector in S are likely to be bounded by the sensors but we ignore such limitations here.
In the following |x| is the L1 norm of the vector x and when k=2 the 2D vector with components x and y is written [x, y]. The output image is called F and we require that the output minimize |ΦF| by choosing F subject to the condition that ΦF = the record formed by the sampling.
Every input pixel is 0 but one which is 1, whose index in j is b.