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]ⁿ. The index set J with n elements is used to select elements (pixels) from one of these images. n is about 2²⁰ 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 ℝⁿ. 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.

k = 0

There are no data or constraints and |ΦF| = 0 and attains this minimum for any F.

k = 1

There is one random subset s₁ of J in Φ. If the bright spot in the input image aligns with a one in this field (b ∊ s₁) then y = [1] and the minimum value for |ΦF| is 1. Any field of pixels in the output image that sums to 1 on s₁ and is 0 elsewhere, satisfies the criterion. Recall that all pixels are non-negative.
If the bright spot in the input image is aligned with a zero then |ΦF| is 0 for any F, but minimizing |F| requires that F = 0.

k = 2

There are two random fields of bits in Φ, s₁ & s₂ and y is one of the equally probable [0, 0], [0, 1], [1, 0] or [1, 1].

y = [0, 0]: |ΦF| is minimized by F=0 which is allowed by constraint ΦF = [0, 0]. The bright pixel was entirely missed by the sampling. |ΦF| is 0 for any F.

y = [1, 0]: |ΦF| is minimized by any field F with non-negative pixels, which sums to 1 and on s₁. If an image were chosen randomly from the normal measure on ℝⁿ then half the image would be a very dark stippled gray; half the points 0 and the other half random and very small. The site of the original bright point would not be black.

y = [0, 1]: Like above but alignment with 2nd field of Φ.

y = [1, 1]: |ΦF| is minimized by a field which sums to 1 and is positive only on s₁ ∩ s₁.

On the average the output image begins to locate the bright pixel.

k = log₂n

At this point we have enough information to locate the bright spot with significant probability.

k = 2¹⁰

Now there will be about 512 ± 20 of the fields of Φ that see the bright pixel. With that many fields viewed as sets, the intersection of about 512 fields is usually a single point, indeed our bright pixel.

If we now consider an input field with two bright pixels things begin to deteriorate. I think we need a program.