## Optimal multiplexed sensing: bounds, conditions and a graph theory link

Optics Express, Vol. 15, Issue 25, pp. 17072-17092 (2007)

http://dx.doi.org/10.1364/OE.15.017072

Acrobat PDF (314 KB)

### Abstract

Measuring an array of variables is central to many systems, including imagers (array of pixels), spectrometers (array of spectral bands) and lighting systems. Each of the measurements, however, is prone to noise and potential sensor saturation. It is recognized by a growing number of methods that such problems can be reduced by multiplexing the measured variables. In each measurement, multiple variables (radiation channels) are mixed (multiplexed) by a code. Then, after data acquisition, the variables are decoupled computationally in post processing. Potential benefits of the use of multiplexing include increased signal-to-noise ratio and accommodation of scene dynamic range. However, existing multiplexing schemes, including Hadamard-based codes, are inhibited by fundamental limits set by sensor saturation and Poisson distributed photon noise, which is scene dependent. There is thus a need to find optimal codes that best increase the signal to noise ratio, while accounting for these effects. Hence, this paper deals with the pursuit of such optimal measurements that avoid saturation and account for the signal dependency of noise. The paper derives lower bounds on the mean square error of demultiplexed variables. This is useful for assessing the optimality of numerically-searched multiplexing codes, thus expediting the numerical search. Furthermore, the paper states the necessary conditions for attaining the lower bounds by a general code. We show that *graph theory* can be harnessed for finding such ideal codes, by the use of strongly regular graphs.

© 2007 Optical Society of America

## 1. Introduction

1. D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE **volume 6065** (2006). [CrossRef]

2. W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. “The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph.” Vib. Spectrosc. **29**:163–170 (2002). [CrossRef]

7. J. F. Turner and P. J. Treado. “Adaptive filtering and hadamard transform imaging spectroscopy with an acousto-optic tunable filter (AOTF).” In Proc. SPIE **volume 2599**, pages 285–293 (1996). [CrossRef]

8. E. E. Fenimore and T. M. Cannon. “Coded aparture imaging with uniformly redundent arrays.” Appl. Opt. **17**:337–347 (1978). [CrossRef] [PubMed]

12. G. K. Skinner. “X-ray imaging with coded masks.” Scientific American **259**:84–89 (1988). [CrossRef] [PubMed]

3. C. Fernandez, B. D. Guenther, M. E. Gehm, D. J. Brady, and M. E. Sullivan. “Longwave infrared (LWIR) coded aperture dispersive spectrometer.” Opt. Express **15**:5742–5753 (2007). [CrossRef] [PubMed]

4. M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. **43**:2965–2974 (2006). [CrossRef]

*multiplexing*[2

2. W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. “The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph.” Vib. Spectrosc. **29**:163–170 (2002). [CrossRef]

7. J. F. Turner and P. J. Treado. “Adaptive filtering and hadamard transform imaging spectroscopy with an acousto-optic tunable filter (AOTF).” In Proc. SPIE **volume 2599**, pages 285–293 (1996). [CrossRef]

23. A. Wuttig. “Optimal transformations for optical multiplex measurements in the presence of photon noise.” Appl. Opt. **44**:2710–2719 (2005). [CrossRef] [PubMed]

*code*. Once the measurements are done, computational demultiplexing derives the sought variable array.

3. C. Fernandez, B. D. Guenther, M. E. Gehm, D. J. Brady, and M. E. Sullivan. “Longwave infrared (LWIR) coded aperture dispersive spectrometer.” Opt. Express **15**:5742–5753 (2007). [CrossRef] [PubMed]

4. M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. **43**:2965–2974 (2006). [CrossRef]

24. Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “Multiplexing for optimal lighting.” IEEE Trans. PAMI **29**:1339–1354 (2007). [CrossRef]

*saturation and photon noise*(the latter is signal-dependent). This can make multiplexing by Hadamard codes counterproductive [19, 24

24. Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “Multiplexing for optimal lighting.” IEEE Trans. PAMI **29**:1339–1354 (2007). [CrossRef]

3. C. Fernandez, B. D. Guenther, M. E. Gehm, D. J. Brady, and M. E. Sullivan. “Longwave infrared (LWIR) coded aperture dispersive spectrometer.” Opt. Express **15**:5742–5753 (2007). [CrossRef] [PubMed]

4. M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. **43**:2965–2974 (2006). [CrossRef]

24. Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “Multiplexing for optimal lighting.” IEEE Trans. PAMI **29**:1339–1354 (2007). [CrossRef]

20. A. Busboom, H. D. Schotten, and H. Elders-Boll. “Coded aperture imaging with multiple measurements.” J. Opt. Soc. Am. A **14**(5):1058–1065 (1997). [CrossRef]

23. A. Wuttig. “Optimal transformations for optical multiplex measurements in the presence of photon noise.” Appl. Opt. **44**:2710–2719 (2005). [CrossRef] [PubMed]

25. V. P. Kozlov and E. V. Sedunov. “Optimization of multiplex measuring systems in the presence of statistical signal fluctuations.” Cybernetics and Systems Analysis **28**:830–839 (1992). [CrossRef]

26. Y. A. Shutova. “Optimization of binary masks for Hadamard-transform optical spectrometers”. J. Opt. Technol. **67**:50–53 (2000). [CrossRef]

20. A. Busboom, H. D. Schotten, and H. Elders-Boll. “Coded aperture imaging with multiple measurements.” J. Opt. Soc. Am. A **14**(5):1058–1065 (1997). [CrossRef]

23. A. Wuttig. “Optimal transformations for optical multiplex measurements in the presence of photon noise.” Appl. Opt. **44**:2710–2719 (2005). [CrossRef] [PubMed]

*lower bounds*on the output noise (estimation error). These bounds indicates how well any general multiplexing code can potentially reduce the noise. Furthermore, we show that in order to attain a lower bound (

*ideal*multiplexing), certain conditions should be satisfied by the multiplexing code. Hadamard codes are special cases of our analysis, hence this work significantly generalizes the known art. This has a major importance, as we explain a way to numerically optimize multiplexing codes under the influence of photo noise, beside saturation and detector noise.

*graph theory*, a large mathematical field, typically distinct from that used in intensity noise analysis. We show that graph theory can be harnessed for finding ideal codes, by using

*strongly regular graphs*.

## 2. Theoretical background

### 2.1. Multiplexing

15. K. C. Lee, J. Ho, and D. J. Kriegman. “Acquiring linear subspaces for face recognition under variable lighting.” IEEE Trans. PAMI **27**:684–698 (2005). [CrossRef]

*N*radiation sources. Let i=(

*i*

_{1},

*i*

_{2}, …,

*i*)

_{N}*be the set of image irradiance values, at a certain pixel. Each element in*

^{t}**i**corresponds to irradiance by any

*individual*source in this setup. Here

*t*denotes transposition.

*N*×

*N*multiplexing matrix

**W**, referred to as a

*multiplexing code*. Each element of its

*m*’th row represents the normalized radiance of a source in the

*m*’th measurement. The radiance of a source is normalized relative to its maximum value. Hence, an element value of 0 states that the source is completely off, while 1 indicates a fully activated source. The sequential measurements acquired at a detector are denoted by the vector

**a**=(

*a*

_{1},

*a*

_{2},…,

*a*)

_{N}*, given by*

^{t}**î**. The best unbiased linear estimator in the sense of mean square error (MSE) for the irradiance corresponding to the individual-sources is

**W**that maximizes the SNR of

**î**, or, equivalently, minimizes MSE

_{î}. Specifically, we seek a lower bound on Eq. (3) and derive conditions on

**W**to attain this bound, hence minimizing MSE

_{î}.

### 2.2. Eigenvalues and singular values

**Definition**Let Λ={λ

*}*

_{f}

^{N}_{f}_{=1}be the set of the eigenvalues (EVs) of a matrix

**W**. The

*multiplicity*of λ

*∊Λ is the number of repetitions of the value λ*

_{f}*in Λ.*

_{f}**Lemma 1**.

*If*

**R**

*and*

**Q**

*are matrices such that*

**RQ**

*is a square matrix, then*[27

27. C. D. Meyer. *Matrix Analysis and Applied Linear Algebra*. SIAM (2000). [CrossRef]

**Lemma 2.**

*Let*

**W**

*be a non-singular N*×

*N matrix. Its EVs are*λ

_{1}≤ … ≤

*λ*.

_{N}*Then*(

*See for example Ref*. [28])

*i*)

*ii*)

*The EVs of*

**W**

^{-1}

*are*

*λ*

^{-1}

*≤ … ≤λ*

_{N}^{-1}

_{1}.

**Definition**

*Let µ*

_{1}≤ µ

_{2}≤ … ≤ µ

*be the EVs of*

_{N}**W**

^{t}**W**. Then, the singular values (SVs) of

**W**, {

*ξ*}

_{f}

^{N}_{f}_{=1}are defined as

**W**is symmetric, then

**W**

^{t}**W**=

**W**

^{2}and

29. M. T. Chu. “A fast recursive algorithm for constructing matrices with prescribed eigenvalues and singular values.” SIAM J. on Numerical Analysis **37**(3):1004–1020 (2000). [CrossRef]

**Theorem 1**. (

*Weyl-Horn*)

*and*

### 2.3. Strongly regular graphs

*G*=(

*V,E*), where

*V*is a set of

*N*vertices. Here

*E*is the set of edges connecting a pair of vertices.

**Definition**Two vertices

*p*,

*q*are said to be

*adjacent or neighbors*if they are connected by an edge.

**Definition**The

*N*×

*N*adjacency matrix Ω of the graph

*G*is composed of elements

**Definition**The

*complement*of a graph

*G*is a graph

*Ḡ*where its adjacency matrix of

**Definition**If all the vertices of

*G*have the same number of neighbors

*k*, then

*G*is

*k-regular*. In this case

**Definition**A

*strongly regular graph*(SRG) [31

31. P. J. Cameron and J. H. V. Lint. *Designs, Graphs, Codes, and Their Links*. Cambridge University Press, New York, NY, USA (1991). [CrossRef]

*N*;

*k*;

*α*;

*β*) is a

*k*-regular graph that has the following properties:

*α*common neighbors (neighbors of both vertices).

*β*common neighbors.

*α*=0. Moreover, vertices 5 and 3 have a single common neighbor, 9, and so are all other analogous pairs. Hence, here

*β*=1.

**Theorem 2**.

*The parameters*(

*N*;

*k*;

*α*;

*β*)

*of a strongly regular graph satisfy*[31

31. P. J. Cameron and J. H. V. Lint. *Designs, Graphs, Codes, and Their Links*. Cambridge University Press, New York, NY, USA (1991). [CrossRef]

*the constraint*

32. J. J. Seidel. “Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3.” Linear Algebra Appl. **1**:281–289 (1968). [CrossRef]

**Theorem 3.**

*Let G be an SRG with parameters*(

*N*;

*k*;

*α*;

*β*).

*Its adjacency matrix*Ω

*has generally three distinct EVs*,

*where*,

*The multiplicity of λ*

^{Ω}

_{3}

*is*1.

## 3. Optimal power-regulated multiplexing

### 3.1. Problem formulation

_{î}under the constraint of a fixed irradiance of an object in each measurement. Such a constraint is desired to avoid saturation of the detector. In saturation, the number of electrons generated in the detector exceeds the capacity of the circuitry that translates it into gray levels. The property of a fixed power is useful for other reasons, such as curbing photon noise, as we shall detail later.

*C*. It is the

*effective*number of radiation sources used in each measurement. This unit-less variable is equivalent to the total radiant power used in a measurement. For example, in Hadamard-based codes,

*C*is equivalent to restricting the power emitted jointly by all sources. Suppose that a multiplexing code

**W**is suggested, such that the irradiance by all the sources exceeds the pre-set threshold. Then this code cannot be used: it yields to much radiation. For example, in a system where saturation occurs if

*C*is greater than

*C*=

_{sat}*N*/5, Hadamard multiplexing cannot be used, since

*C*

_{Had}exceeds

*C*

_{sat}in this case.

**W**violates the fixed-power constraint, what can be done? A trivial way is to equally reduce the power of each of the sources. However, refs. [18, 22] proved that such a step should be avoided. A better solution is to modify

**W**, such that its corresponding

*C*would comply with the constraint. Such a modification, however, is not easy to accomplish. The reason is that current codes in the literature [9, 23

**44**:2710–2719 (2005). [CrossRef] [PubMed]

*C*out of

*N*sources. Specifically, Hadamard codes are too limited: according to Eq. (19), these codes totally couple

*C*to

*N*. This raises the need to extend the set of multiplexing codes, to comply with a general constraint on the effective number of simultaneously activated sources

*C*.

*i.e*.

_{î}. To simplify the analysis, we slightly modify the problem for the moment, and define the cost function

_{î}, if σ

^{2}

*is constant. The influence of σ*

_{a}^{2}

*will be discussed in Sec. 7.*

_{a}**W**to solve Eqs. (23,24,25,26).

### 3.2. Conditions for a global optimum

**W**. Such conditions allow us to identify an optimal solution to the problem, if a potential solution is encountered. Indeed, later on in Sec. 6 we show that these conditions are satisfied by matrices

**W**originally developed in graph theory. We can also apply these conditions to verify if a matrix reached by numerical optimization is indeed the global optimum.

**W**.

#### 3.2.1. The cost as a function of singular values

**W**. Recall from definition 2.2 that

*µ*

_{1}≤ … ≤

*µ*are the EVs of

_{N}**W**

^{t}**W**. Then using, Lemma 2,

**W**. This will allow us to better streamline (24,25,26) into Eq. (27), forming a lower bound on

**W**, we cite the following theorem [33]:

**Theorem 4.**

*Let*

**W**

*be constrained by*

*Eqs*. (24,25,26).

*Then, C is an EV of*

**W**.

*Furthermore, let λ*

_{f}*be an EV of*

**W**.

*Then*, |

*λ*|≤

_{f}*C*. The proof is given in App. A.

**W**. This has an implication to its corresponding SVs, which are used in (27). This implication stems from Theorem 1. Let us set

*f*=

*N*in Eq. (8). Then,

#### 3.2.2. Optimality of the singular values

_{î}. To achieve this, we have first expressed

**W**. Define the vector

*µ*

_{1},

*µ*

_{2}, …,

*µ*). We now seek to minimize Eq. (32) as a function of

_{N}*, while the rest are constant. Can we do this arbitrarily? The answer is*μ →
, µ

_{f}*no*. The reason is that Eqs. (24,25,26) bound the domain of

**W**, hence bounding the domain of its SVs. Therefore, any

*µ*cannot be arbitrarily increased; the elements of

_{f}*S*≡Const,

*µ*

*. Let*

_{N}*µ*

*be decreased by some small quantity Δ*

_{N}*µ*

*. Then, to conserve*

_{N}*S*in Eq. (33), the value of at least one other

*µ*should increase. An increase of

_{f}*µ*

*by Δ*

_{f}*µ*

*reduces*

_{N}*µ*

*is the smallest element of the set {*

_{f}*µ*}

_{f}^{N-1}

_{f=1}. The smallest element in this set is µ

_{1}. Overall, decreasing µ

*N*by Δµ

*while increasing µ*

_{N}_{1}by Δµ

*yields a net reduction of*

_{N}*for µ*

_{N}_{1}delivers a net benefit in

*, then µ*

_{N}*should be as low as possible. From Eq. (31), the lowest possible value of µ*

_{N}*is*

_{N}*C*

^{2}. To conclude,

**Corollary 1**.

*In an optimal multiplexing code*

**W**,

*the largest SV satisfies*

*, we turn to the other elements of*

_{N}*µ*}

_{f}^{N-1}

_{f=1}.

*The inequality of means*[34

34. M. Alicacute, B. Mond, J. Pecbreve aricacute, and V. Volenec. “The arithmetic-geometric-harmonic-mean and related matrix inequalities.” Linear Algebra and its Applications **264**(1):55–62 (1997). [CrossRef]

*B*is the lower bound of

*B*is constant as long as S is fixed. We wish that

*µ*}

_{f}^{N-1}

_{f=1}are all equal. Therefore, using Eq. (6), the elements of the set {

*ξ*}

_{f}^{N-1}

_{f=1}are also equal. We recap with the following corollary.

**Corollary 2**.

*An ideal multiplexing matrix*

**W**

*is such, that all its SVs (but the largest one)*{

*ξ*}

_{f}^{N-1}

_{f=1}

*are equal to each other. Its largest SV equals C*.

*B*as

*ideal*. It is not guaranteed however, that such matrices exist for all values of

*N*and

*C*. Matrices that minimize

*B*are simply referred to as

*optimal*.

#### 3.2.3. The ideal variable S

*S*, the MSE is minimized by matrices that comply with the terms in Corollary 2. We now relieve the constraint of an arbitrarily fixed

*S*. Hence,

*S*may vary (see Fig. 2). Furthermore, we derive the best value for

*S*. This yields a condition on the elements of

**W**. Following Lemma 1,

**WW**

*are*

^{t}*B*is minimized by using the largest

*S*possible. Hence,

*if*and

*only if*equality also holds in Eq. (46). Trivially, this happens if all elements of

**W**are either 1’s or 0’s. In this case Eq. (49) yields Eq. (51), alleviating the need for an arbitrarily fixed

*S*.

*w*∊{0,1}∀

_{m,s}*. In other words,*

_{m, s}*B*reaches its lowest potential value

*B*

_{min}(

*C*), if

*S*is given by Eq. (51).

**Corollary 3**.

*The lower bound*

*B*

_{min}

*of*

*is achieved using binary multiplexing matrices*

**W**.

**Theorem 5**.

*yields B*

_{min}

*only if C*∊ℤ

^{+}.

**Theorem 6**.

*Equality in Eq. (54) is obtained by a matrix*

**W**,

*if and only if this matrix complies with both Corollaries 2 and 3*.

*B*

_{min}determines the behavior of MSE

_{î}as a function of both

*N*and

*C*. Furthermore, if

**W**satisfies the optimality conditions, then σ

^{2}

_{a}*B*

_{min}is exactly the expected value of MSE

_{î}. In Fig. 4 we illustrate the behavior of

*B*

_{min}for a specific value of

*N*and a range of values of

*C*.

## 4. The case of a free variable C

*C*. It introduced the lower bound on MSE

_{î}for all pairs of {

*N*,

*C*}, via Eqs. (53,54). However, what happens if

*C*is a free variable in the domain

*C*∊[1,

*N*]? For a given

*N*, which value of

*C*∊[1,

*N*] minimizes MSE

_{î}? This is discussed in this section.

_{î}is influenced by

*C*through three mechanisms.

*C*affects the EVs of the optimal

**W**. This effect is reflected in the presence of

*C*in the term for the bound

*B*

_{min}(see Eq. 53).

*C*may not be free to vary through all the domain [1,

*N*] due to saturation. There may exist

*C*

_{sat}such that ∀

*C*>

*C*

_{sat}, elements of the vector

**a**(Eq. 1) become saturated. Such elements of

**a**prevent the correct reconstruction of

**î**by Eq. (2).

*C*may affect σ

*in Eq. (3). So far in this paper, there was no consideration of variations in σ*

_{a}*with respect to*

_{a}*C*. We shall see in Sec. 7 that this is often not the case,

*e.g*. due to photon noise.

*C*. The other mechanisms are discussed in later sections. This allows the current section to compare our results to prior codes that do not consider mechanisms 2 and 3 as well, specifically, Hadamard codes [9, 18].

### 4.1. Minimization of Bmin

*C*is free to vary, then optimal matrices

**W**are based on the Hadamard matrices and are known as the

**S**-matrices [9]. These matrices indeed comply with the conditions of Theorem 6. However,

**S**-matrices exist only for a subset of the possible values of

*N*.

*C*that minimizes Eq. (53) is defined as

*C*

^{free}

_{opt}is not an integer. If it is not an integer, then it does not satisfy Theorem 5. Hence, this value does not correspond to a multiplexing matrix that meets the bound

*B*

_{min}(

*C*

^{free}

_{opt}). Nevertheless, Cfreeopt is important: it may imply an integer

*C*(close to

*C*

^{free}

_{opt}) that is associated with an ideal multiplexing matrix.

*C*

^{free}

_{opt}is unique. To satisfy Theorem 5, only integer

*C*can be used. Let us define

*C*

_{opt}. Define the integer domain

*C*

^{int}

_{opt}satisfies

### 4.2. Consistency with Hadamard matrices

*C*

^{int}

_{opt}degenerates to

*C*

_{Had}. It can be shown that

*N*that correspond to

**S**matrices. This is consistent with Ref. [9], which proves the optimality of Hadamard based-codes. Hence, Eq. (61) indeed holds in these cases.

*B*

_{min}(

*C*

_{Had}).

*N*,

*C*}) for which Hadamard-based codes do not exist.

*optimal multiplexing*codes do not necessitate an integer

*C*. When the condition specified in Theorem 5 is not met, then

*B*≠

*B*

_{min}. Thus, for a non-integer

*C*, no matrix

**W**is

*ideal*, but a certain

**W**can still be

*optimal, i.e*. minimizing

## 5. Saturation

*C*influences MSE

_{î}. It is saturation. Due to saturation,

*C*cannot exceed

*C*

_{sat}. In this section we discuss seeking an optimal value of

*C*, under the saturation constraint.

*C*is

*C*

^{free}

_{opt}≤

*C*

_{sat}, where

*C*

^{free}

_{opt}is defined in Eq. (58). In this case,

*C*

^{free}

_{opt}∊Ψ

^{sat}. Since

*C*

^{free}

_{opt}uniquely minimizes Eq. (53) in this domain, the optimal solution degenerates to that described in Sec. 4.1.

*C*

^{free}

_{opt}>

*C*

_{sat}, i.e,

*C*

^{free}

_{opt}/∊Ψ

^{sat}. Then, there is no value of

*C*∊Ψ

^{sat}at which the derivative of

*B*

_{min}(

*C*) is null. Hence, the global minimum of the function

*B*

_{min}(

*C*) is obtained at the constraint

*C*

_{sat}. This is illustrated, for example, in Fig. 4. To conclude,

## 6. Some ideal solutions

*ideal*codes exist. The familiar Hadamard-based

**S**matrices are ideal codes. Their value of

*B*

_{min}(

*C*

_{Had}). Are there other matrices, that satisfy these optimality conditions, for other values of {

*N*,

*C*}? In the following, we show that indeed there is a class of such matrices.

### 6.1. Strongly regular graphs as a solution

**W**, sought in Sec. 3, as we now detail:

**W**is

*C*, with multiplicity which is generally 1 (See Corollary 2). Similarly, the highest SV of Ω is

*k*, with the same multiplicity. Hence, we set

*k*=

*C*.

*α*=

*β*in Eqs. (14,15) yields

*k*. Namely,

**Theorem 7.**

*Let Ω be the adjacency matrix of a*(

*N;C;α;α*)

*strongly regular graph. Then*, Ω

*is an ideal matrix*

**W**

*solving*

*Eqs*. (23,24,25,26).

*α*=

*β*as in Theorem 7, then Eq. (13) takes the following form

37. G. Royle. “Strongly regular graphs” (1996) http://people.csse.uwa.edu.au/gordon/remote/srgs/index.html

36. T. Spence. “Strongly Regular Graphs on at most 64 vertices” http://www.maths.gla.ac.uk/es/srgraphs.html

37. G. Royle. “Strongly regular graphs” (1996) http://people.csse.uwa.edu.au/gordon/remote/srgs/index.html

### 6.2. Solutions from complement graphs

**W**. Such a set may be derived indirectly from another set of SRGs. Refs. [31

31. P. J. Cameron and J. H. V. Lint. *Designs, Graphs, Codes, and Their Links*. Cambridge University Press, New York, NY, USA (1991). [CrossRef]

**Theorem 8**.

*A graphG is strongly regular with parameters (N;k;α;β) if and only if its complement Ḡ is also strongly regular, with parameters (N ;N-k-1;N-2k+β-2;N-2k+α)*.

*Ḡ*with some parameters (

*N; C̄;*α ^
;α ¯ +2), there exists a complement SRG,

*G*, with parameters (

*N;C;α;α*). Here

*C*=

*N-C̄*-1 and α=

*N-2C̄*+

*. Hence, using Theorem 7,*α ¯

*G*is a solution for Eqs. (23,24,25,26).

### 6.3. A simulated example

**i**represents noiseless graylevel measurements, where each element of the array expresses the radiance in a narrow spectral band, as transmitted through the atmosphere. As “ground-truth”

**i**, we took the data in [38

38. P. Puxley and T. Geballe. “Transmission Spectra” (1999) http://www.gemini.edu/sciops/ObsProcess/obsConstraints/ocTransSpectra.html

_{a}=8 graylevels independent of the signal, and quantized by an 8-bit camera, having a range of [0,255] graylevels. The resulting absolute error |

*î*-

*i*| for this trivial measurement process is plotted by a red line in Fig. 7b.

*N*=45. Thus, we used the adjacency matrix shown in Fig. 6 for multiplexing the spectral bands. Thus, in each measurement, 12 narrow spectral bands were simultaneously sensed. Then, noise and quantization were applied as in the standard acquisition process. There was no saturation in

**a**: considering the values

**i**plotted in Fig. 7a, all elements of

**a**were lower than 255 graylevels. The measurements were then demultiplexed, yielding a less noisy estimate

**î**. The resulting absolute error |

*î*-

*i*| of the demultiplexed values is plotted by a green line in Fig. 7b. Indeed, the noise is significantly reduced. Quantitatively, the noise reduction is as expected: empirically, MSE

_{î}is 6.96 squared-graylevels, when averaged over many such randomly noised simulations. This is consistent with the expected theoretical value of MSE

_{î}, obtained by Eqs. (53,54).

## 7. Photon noise

*C*influences MSE

_{î}, as mentioned in Sec. 4. Here we deal with the presence of photon noise in the acquired measurements. Generally, photon noise inhibits the multiplexing gain. The variance of photon noise increases linearly with the acquired signal. Hence, an increase of radiance used in each measurement increases the noise. This effect degrades the multiplexing gain, sometimes even causing it to be counterproductive [22, 24

**29**:1339–1354 (2007). [CrossRef]

### 7.1. The affine noise model

*affine noise model*. It exists in high grade detectors, which have a linear radiometric response. The noise can be divided into two components, signal-dependent and signal-independent. Regardless of the photon flux, signal-independent noise is created by dark current [24

**29**:1339–1354 (2007). [CrossRef]

^{2}

_{gray}.

*𝓔*denotes expectation. This variance linearly increases with the measured electric signal

*n*

^{photo}

_{electr}. The number of detected electrons

*n*

^{photo}

_{electr}is proportional to the gray-level of the acquired pixel value

*a*

*Q*

_{electr}is the number of photo-generated electrons required to change a unit gray-level. Typically

*Q*

_{electr}≫1. Combining Eqs. (71,72) yields a variance in gray levels

**29**:1339–1354 (2007). [CrossRef]

*i*. Following Eqs. (1) and (20), in each measurement the acquired value is

_{s}^{2}≈

*i*/

_{s}*Q*

_{electr}is the photon noise variance, induced by

*i*

*. Eq. (76) is an affine function of the number of active sources*

_{s}*C*. This was demonstrated experimentally in Ref. [22]. The parameters κ

^{2}

_{gray}and η

^{2}depend on the setup hardware. A way to calibrate them is described in Ref. [22].

### 7.2. Optimal multiplexing

*C*, termed

*C*

^{final}

_{opt}, accounting for all the effects. These include the various noise mechanisms and saturation. In addition, the section describes an approach to obtain a multiplexing matrix

**W**that corresponds to

*C*

^{final}

_{opt}.

_{î}expression given in Eq. (78). It consists of the following steps.

*C*values from 1 to

*C*

^{sat}

_{opt}, where

*C*

^{sat}

_{opt}is defined in Eq. (68). For each value of

*C*, perform the subsequent steps 2 and 3.

**W**(

*C*) that optimizes

**W**(

*C*

^{final}

_{opt}).

_{î}(

*C*) for all

*C*∊[1,

*C*

^{sat}

_{opt}]. The reason is that MSE

_{î}(

*C*) is well behaved [22], hence one can incorporate efficient optimization procedures. The core of the process is step 2. In Ref. [22], this minimization was based on a numerical search of

**W**(

*C*) using adjacency matrices of known SRGs having the proper parameters (see Sec. 6). In this way, step 2 avoids numerical search altogether. However, SRGs are not available for every {

*N*,

*C*} set. Thus, numerical optimization may still be needed. Nevertheless, there is a second, more general way by which step 2 is simplified:

*B*

_{min}(

*C*) can set the termination of a numerical search, as is explained in the following.

*l*’th iteration, there is a matrix

**W**

*that complies with Eqs. (24,25,26). Based on Eq. (22), a corresponding value*

_{l}*l*+1, the multiplexing matrix changes to

**W**

_{l}_{+1}, with a corresponding

**W**

_{l}) is given in closed-form (See [22]).

*l*does

**W**

*yield*

_{l}*B*

_{min}(

*C*) can terminate the iterations. If at the

*l*’th iteration

**W**

*is as good as it can get. Hence, it can be set as*

_{l}**W**(

*C*) in step 2 above.

## 8. Discussion

*B*given in Eq. (43) determines best feasible performance by any code for which the sum of SVs is arbitrarily fixed. Correspondingly, Corollary 2 states the structure of desired codes. A stronger bound is

*B*

_{min}(

*C*), given by Eq. (53), as it states the best conceivable performance of any code, whatever its SVs are. However, finding a code that attains

*B*

_{min}(

*C*) is more difficult, since such a code is constrained to satisfy Eqs. (48,51). Such a constraint can only be satisfied by binary codes (Corollary 3). This lead to an interesting link to graph theory, which is usually a field distinct from analysis of intensity noise. We showed that SRG have adjacency matrices that are ideal, in the sense that they attain

*B*

_{min}(

*C*).

*N*, activated sources

*C*, and be tailored to the characteristics of noise and saturation.

**W**is helpful to subcases of such matrices, be they binary [3

**15**:5742–5753 (2007). [CrossRef] [PubMed]

**43**:2965–2974 (2006). [CrossRef]

12. G. K. Skinner. “X-ray imaging with coded masks.” Scientific American **259**:84–89 (1988). [CrossRef] [PubMed]

26. Y. A. Shutova. “Optimization of binary masks for Hadamard-transform optical spectrometers”. J. Opt. Technol. **67**:50–53 (2000). [CrossRef]

8. E. E. Fenimore and T. M. Cannon. “Coded aparture imaging with uniformly redundent arrays.” Appl. Opt. **17**:337–347 (1978). [CrossRef] [PubMed]

20. A. Busboom, H. D. Schotten, and H. Elders-Boll. “Coded aperture imaging with multiple measurements.” J. Opt. Soc. Am. A **14**(5):1058–1065 (1997). [CrossRef]

**44**:2710–2719 (2005). [CrossRef] [PubMed]

**29**:1339–1354 (2007). [CrossRef]

**W**

^{offset}is 0. In other words, det(

**W**

^{offset})=0. By the definition in (80), this means that det(

**W**-

*C*

**I**)=0,

*i*.

*e*.,

*C*is an EV of

**W**. This proves the first part of Theorem 4. Suppose that

**u**

*=(*

^{f}*u*

^{f}_{1},…,

*u*)

^{f}_{N}*is an eigenvector corresponding to*

^{t}*λ*. Without the loss of generality, we may normalize

_{f}**u**

*, such that*

^{f}**u**

*is an eigenvector of*

^{f}**W**. Hence,

## Acknowledgments

## References and links

1. | D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk. “A new compressive imaging camera architecture using optical-domain compression.” In Proc. SPIE |

2. | W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. “The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph.” Vib. Spectrosc. |

3. | C. Fernandez, B. D. Guenther, M. E. Gehm, D. J. Brady, and M. E. Sullivan. “Longwave infrared (LWIR) coded aperture dispersive spectrometer.” Opt. Express |

4. | M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. “Static two-dimensional aperture coding for multimodal, multiplex spectroscopy.” Appl. Opt. |

5. | Q. S. Hanley, D. J. Arndt-Jovin, and T. M. Jovin. “Spectrally resolved fluorescence lifetime imaging microscopy.” Appl. Spectrosc. |

6. | G. Nitzsche and R. Riesenberg. “Noise, fluctuation and HADAMARD-transform-spectrometry.” In Proc. SPIE |

7. | J. F. Turner and P. J. Treado. “Adaptive filtering and hadamard transform imaging spectroscopy with an acousto-optic tunable filter (AOTF).” In Proc. SPIE |

8. | E. E. Fenimore and T. M. Cannon. “Coded aparture imaging with uniformly redundent arrays.” Appl. Opt. |

9. | M. Harwit and N. J. A. Sloane. |

10. | T. M. Palmieri. “Multiplex methods and advantages in X-ray astronomy.” Astrophysics and Space Science |

11. | R. J. Proctor, G. K. Skinner, and A. P. Willmore. “The design of optimum coded mask X-ray telescopes.” Royal Astronomical Society, Monthly Notices |

12. | G. K. Skinner. “X-ray imaging with coded masks.” Scientific American |

13. | A. M. Bronstein, M. M. Bronstein, E. Gordon, and R. Kimmel. “Fusion of 2d and 3d data in three-dimensional face recognition.” In Proc. IEEE ICIP |

14. | O. G. Cula, K. J. Dana, D. K. Pai, and D. Wang. “Polarization multiplexing and demultiplexing for appearance-based modeling.” IEEE Trans. PAMI |

15. | K. C. Lee, J. Ho, and D. J. Kriegman. “Acquiring linear subspaces for face recognition under variable lighting.” IEEE Trans. PAMI |

16. | M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas. “Synthetic aperture confocal imaging.” ACM TOG |

17. | F. Moreno-Noguer, S. K. Nayar, and P. N. Belhumeur. “Optimal illumination for image and video relighting.” In Proc. CVMP pages 201–210 (2005). |

18. | Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “A theory of multiplexed illumination.” In Proc. IEEE ICCV |

19. | A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec. “Performance relighting and reflectance transformation with time-multiplexed illumination.” ACM TOG |

20. | A. Busboom, H. D. Schotten, and H. Elders-Boll. “Coded aperture imaging with multiple measurements.” J. Opt. Soc. Am. A |

21. | E. E. Fenimore. “Coded aperture imaging: predicted performance of uniformly redundant arrays.” Appl. Opt. |

22. | N. Ratner and Y. Y. Schechner. “Illumination multiplexing within fundamental limits.” In Proc. IEEE CVPR (2007). |

23. | A. Wuttig. “Optimal transformations for optical multiplex measurements in the presence of photon noise.” Appl. Opt. |

24. | Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur. “Multiplexing for optimal lighting.” IEEE Trans. PAMI |

25. | V. P. Kozlov and E. V. Sedunov. “Optimization of multiplex measuring systems in the presence of statistical signal fluctuations.” Cybernetics and Systems Analysis |

26. | Y. A. Shutova. “Optimization of binary masks for Hadamard-transform optical spectrometers”. J. Opt. Technol. |

27. | C. D. Meyer. |

28. | R. A. Horn and C. R. Johnson. |

29. | M. T. Chu. “A fast recursive algorithm for constructing matrices with prescribed eigenvalues and singular values.” SIAM J. on Numerical Analysis |

30. | R. Diestel. |

31. | P. J. Cameron and J. H. V. Lint. |

32. | J. J. Seidel. “Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3.” Linear Algebra Appl. |

33. | W. Haemers. “Matrix techniques for strongly regular graphs and related geometries.” Intensive Course on Finite Geometry and its Applications, University of Ghent (2000). |

34. | M. Alicacute, B. Mond, J. Pecbreve aricacute, and V. Volenec. “The arithmetic-geometric-harmonic-mean and related matrix inequalities.” Linear Algebra and its Applications |

35. | K. Coolsaet and J. Degraer. “The strongly regular (45,12,3,3) graphs.” Elec. Journ. Combin13(1) (2006). |

36. | T. Spence. “Strongly Regular Graphs on at most 64 vertices” http://www.maths.gla.ac.uk/es/srgraphs.html |

37. | G. Royle. “Strongly regular graphs” (1996) http://people.csse.uwa.edu.au/gordon/remote/srgs/index.html |

38. | P. Puxley and T. Geballe. “Transmission Spectra” (1999) http://www.gemini.edu/sciops/ObsProcess/obsConstraints/ocTransSpectra.html |

39. | S. Ioué and K. R. Spring. |

40. | C. Liu, W. T. Freeman, R. Szeliski, and S. B. Kang. “Noise estimation from a single image.” In Proc. CVPR |

41. | F. Alter, Y. Matsushita, and X. Tang. “An intensity similarity measure in low-light conditions.” In Proc. ECCV |

42. | H. H. Barrett and W. Swindell. |

**OCIS Codes**

(030.4280) Coherence and statistical optics : Noise in imaging systems

(110.6980) Imaging systems : Transforms

(150.2950) Machine vision : Illumination

(300.6380) Spectroscopy : Spectroscopy, modulation

(340.7430) X-ray optics : X-ray coded apertures

(110.1758) Imaging systems : Computational imaging

**ToC Category:**

Imaging Systems

**History**

Original Manuscript: September 4, 2007

Revised Manuscript: November 13, 2007

Manuscript Accepted: November 14, 2007

Published: December 5, 2007

**Citation**

Netanel Ratner, Yoav Y. Schechner, and Felix Goldberg, "Optimal multiplexed sensing: bounds, conditions and a graph theory link," Opt. Express **15**, 17072-17092 (2007)

http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-15-25-17072

Sort: Year | Journal | Reset

### References

- D. Takhar, J. N. Laska, M. B. Wakin, M. F. Duarte, D. Baron, S. Sarvotham, K. F. Kelly, and R. G. Baraniuk, "A new compressive imaging camera architecture using optical-domain compression," Proc. SPIE 6065, (2006). [CrossRef]
- W. G. Fateley, R. M. Hammaker, R. A. DeVerse, R. R. Coifman, and F. B. Geshwind. "The other spectroscopy: demonstration of a new de-dispersion imaging spectrograph," Vib. Spectrosc. 29,163-170 (2002). [CrossRef]
- C. Fernandez, B. D. Guenther, M. E. Gehm, D. J. Brady, and M. E. Sullivan. "Longwave infrared (LWIR) coded aperture dispersive spectrometer," Opt. Express 15,5742-5753 (2007). [CrossRef] [PubMed]
- M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan. "Static two-dimensional aperture coding for multimodal, multiplex spectroscopy," Appl. Opt. 43,2965-2974 (2006). [CrossRef]
- Q. S. Hanley, D. J. Arndt-Jovin, and T. M. Jovin. "Spectrally resolved fluorescence lifetime imaging microscopy," Appl. Spectrosc. 56, 63-84 (2002). [CrossRef]
- G. Nitzsche and R. Riesenberg. "Noise, fluctuation and HADAMARD-transform-spectrometry," In Proc. SPIE 5111, 273-282 (2003). [CrossRef]
- J. F. Turner and P. J. Treado. "Adaptive filtering and hadamard transform imaging spectroscopy with an acoustooptic tunable filter (AOTF)," Proc. SPIE 2599, 285-293 (1996). [CrossRef]
- E. E. Fenimore and T. M. Cannon. "Coded aparture imaging with uniformly redundent arrays," Appl. Opt. 17,337-347 (1978). [CrossRef] [PubMed]
- M. Harwit and N. J. A. Sloane, Hadamard Transform Optics, (Academic Press, New York, 1979).
- T. M. Palmieri, "Multiplex methods and advantages in X-ray astronomy," Astrophys. Space Sci. 28,277-287 (1974). [CrossRef]
- R. J. Proctor, G. K. Skinner, and A. P. Willmore, "The design of optimum coded mask X-ray telescopes," Royal Astron. Soc. Monthly Notices 187,633-643 (1979).
- G. K. Skinner. "X-ray imaging with coded masks," Sci. Am. 259,84-89 (1988). [CrossRef] [PubMed]
- A. M. Bronstein, M. M. Bronstein, E. Gordon, and R. Kimmel, "Fusion of 2d and 3d data in three-dimensional face recognition," In Proc. IEEE ICIP Vol. 1, pages 87-90 (2004).
- O. G. Cula, K. J. Dana, D. K. Pai, and D. Wang, "Polarization multiplexing and demultiplexing for appearancebased modeling," IEEE Trans. PAMI 29,362-367 (2007). [CrossRef]
- K. C. Lee, J. Ho, and D. J. Kriegman, "Acquiring linear subspaces for face recognition under variable lighting," IEEE Trans. PAMI 27,684-698 (2005). [CrossRef]
- M. Levoy, B. Chen, V. Vaish, M. Horowitz, I. McDowall, and M. Bolas, "Synthetic aperture confocal imaging," ACM TOG 23,825-834 (2004).
- F. Moreno-Noguer, S. K. Nayar, and P. N. Belhumeur, "Optimal illumination for image and video relighting," In Proc. CVMP pages 201-210 (2005).
- Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur, "A theory of multiplexed illumination," In Proc. IEEE ICCV Vol. 2, pages 808-815 (2003).
- A. Wenger, A. Gardner, C. Tchou, J. Unger, T. Hawkins, and P. Debevec, "Performance relighting and reflectance transformation with time-multiplexed illumination," ACM TOG 24,756-764 (2005).
- A. Busboom, H. D. Schotten, and H. Elders-Boll, "Coded aperture imaging with multiple measurements," J. Opt. Soc. Am. A 14,1058-1065 (1997). [CrossRef]
- E. E. Fenimore, "Coded aperture imaging: predicted performance of uniformly redundant arrays," Appl. Opt. 17,3562-3570 (1978). [CrossRef] [PubMed]
- N. Ratner and Y. Y. Schechner, "Illumination multiplexing within fundamental limits," In Proc. IEEE CVPR (2007).
- A. Wuttig, "Optimal transformations for optical multiplex measurements in the presence of photon noise," Appl. Opt. 44,2710-2719 (2005). [CrossRef] [PubMed]
- Y. Y. Schechner, S. K. Nayar, and P. N. Belhumeur, "Multiplexing for optimal lighting," IEEE Trans. PAMI 29,1339-1354 (2007). [CrossRef]
- V. P. Kozlov and E. V. Sedunov, "Optimization of multiplex measuring systems in the presence of statistical signal fluctuations," Cybern. Syst. Anal. 28,830-839 (1992). [CrossRef]
- Y. A. Shutova, "Optimization of binary masks for Hadamard-transform optical spectrometers," J. Opt. Technol. 67,50-53 (2000). [CrossRef]
- C. D. Meyer. Matrix Analysis and Applied Linear Algebra, (SIAM 2000). [CrossRef]
- R. A. Horn and C. R. Johnson, Matrix Analysis, (Cambridge, New York, 1985).
- M. T. Chu, "A fast recursive algorithm for constructing matrices with prescribed eigenvalues and singular values," SIAM J. on Numerical Analysis 37,1004-1020 (2000). [CrossRef]
- R. Diestel, Graph Theory, 3rd edition (Springer, 2000).
- P. J. Cameron and J. H. V. Lint, Designs, Graphs, Codes, and Their Links, (Cambridge University Press, New York, NY, USA, 1991). [CrossRef]
- J. J. Seidel, "Strongly regular graphs with (-1, 1, 0) adjacency matrix having eigenvalue 3," Numer. Linear Algebra Appl. 1,281-289 (1968). [CrossRef]
- W. Haemers, "Matrix techniques for strongly regular graphs and related geometries," Intensive course on Finite Geometry and its Applications, University of Ghent (2000).
- M. Alicacute, B. Mond, J. Pecbreve aricacute and V. Volenec, "The arithmetic-geometric-harmonic-mean and related matrix inequalities," Numer. Linear Algebra Appl. 264,55-62 (1997). [CrossRef]
- K. Coolsaet and J. Degraer, "The strongly regular (45,12,3,3) graphs," Electron. J. Comb. 13, (2006).
- T. Spence. "Strongly Regular Graphs on at most 64 vertices" http://www.maths.gla.ac.uk/ es/srgraphs.html
- G. Royle, "Strongly regular graphs," (1996). http://people.csse.uwa.edu.au/gordon/remote/srgs/index.html
- P. Puxley and T. Geballe, "Transmission Spectra," (1999) http://www.gemini.edu/sciops/ObsProcess/obsConstraints/ocTransSpectra.html
- S. Ioué and K. R. Spring, Video Microscopy, 2nd ed., (Plenum Press, New York, 1997) chaps. 6, 7, 8.
- C. Liu, W. T. Freeman, R. Szeliski, and S. B. Kang, "Noise estimation from a single image," In Proc. CVPR 1, 901-908 (2006).
- F. Alter, Y. Matsushita, and X. Tang, "An intensity similarity measure in low-light conditions," In Proc. ECCV 4, 267-280 (2006).
- H. H. Barrett and W. Swindell, Radiological Imaging, (Academic press, New York 1981) Vol. 1.

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article | Next Article »

OSA is a member of CrossRef.