Bednorz W. (ed.) Advances in Greedy Algorithms

Подождите немного. Документ загружается.

Greedy Methods in Plume Detection, Localization and Tracking

321

These observations suggest that the l

-regularized least squares method is effective in joint

model selection and parameter estimation for instantaneous source release.

Fig. 3. Sensor readings for a single source with instantaneous release.

Table 1. Comparison of Model Selection and Source Localization Accuracy with Different

Regularization Methods

3.5.3 Model mismatch to continuous release source

Consider a single source located at (-40, 35, 12) with continuous release rate

One realization of the concentration readings from the five sensors is shown in Fig. 5. Note

that the concentration readings from sensors 2-5 have not reached their peaks by the end of

the samples. This will in general make the source parameter estimation more difficult. In 100

realizations, the l

-regularized least squars method with p = 1 identified one source in 92

times and two sources in 8 times with their estimated locations close to each other. The

incorrect identification of model order is due to the abrupt release at two time instances

t = 10 and t = 50 with exponential decay of the release rate. The root mean square error of

the estimated source location is 15.4 using the estimates from the correctly identified cases.

Clearly, the l

-regularized least squares method can tolerate slight model mismatch when

the release rate sequence is not overly sparse.

Advances in Greedy Algorithms

322

Fig. 4. Sensor readings for two sources, each with instantaneous release.

Fig. 5. Sensor readings for one source with continuous release.

4. Discussion and conclusions

In this chapter, we studied plume detection, localization and tracking problem with two

different settings. For plume mapping with binary detection sensors, we formulated the

problem as finding the most likely state sequence based on a fuzzy hidden Markov model.

Greedy Methods in Plume Detection, Localization and Tracking

323

Under the assumption that each sensor has high detection and low false alarm probability, we

proposed a greedy heuristic decoding algorithm with much less computational cost than the

well known Viterbi algorithm. The plume localization accuracy of our algorithm is close to the

optimal decoder using Viterbi algorithm when tracking a single plume using randomly

deployed sensors. Our algorithm is applicable to general decoding problem over a long

observation sequence when the localization error probability of the Viterbi decoder is small.

There is a serious drawback of using FHMM for plume tracing. In our FHMM formulation,

one can not distinguish whether a plume existence state is due to source releasing or plume

propagation without knowing the whole state sequence. Thus one has to make tradeoff

between the delay and localization accuracy. A refined plume propagation model based on

more accurate sensor readings and contaminant transport physics was then used for source

localization and release rate sequence estimation. When localizing unknown number of

sources based on the observation of aggregated concentrations, we proposed an l

regularized least squares method to estimate the location and release rate of atmospheric

pollution. For 0 ≤ p ≤ 1, the method enforces sparsity of the release sequence of each

identified source. The proposed greedy method can identify multiple sources of

instantaneous release type and can also localize sources of continuous release. The accuracy

of source parameter estimation has been examined for the cases where the number of

sources and the corresponding locations are unknown.

In general, the least squares approach does not provide any measure of the estimation error.

However, one can examine the residual and make additional assumptions such as additive

Gaussian noise in order to quantify the covariance of the localization error. Through

simulation study, we found that the proposed method is effective in localizing instantaneous

release sources and has certain degree of tolerance to model mismatch. It is worth noting that

the sensor locations, sampling rate and measurement accuracy can affect the source

localization performance significantly. Finding the best sensor placement and sensing strategy

in a given surveillance area is another important research theme and demands future work.

We hope that with the advances in the development of greedy algorithms, many other

challenging optimization tasks can be tackled with efficient and near optimal solutions.

5. References

[1] S. Boyd, and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.

[2] S. M. Brennan, A. M. Mielke, and D. C. Torney, “Radiation Detection with Distributed

Sensor Networks,” IEEE Computer, pp. 57-59, August 2004.

[3] S. M. Brennan, A. M. Mielke, and D. C. Torney, “Radioactive Source Detection by Sensor

Networks,” IEEE Nuclear Science, 52(3), pp. 813-819, 2005.

[4] E. J. Candes and T. Tao,”The Dantzig Selector: Statistical Estimation When p Is Much

Larger Than n,” submitted to Annals of Statistics, 2005.

[5] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, first edition,

MIT Press and McGraw-Hill, 1990.

[6] T. M. Cover, and J. A. Thomas, Elements of Information Theory, New York: Wiley, 1991.

[7] R. Chartrand, “Exact Reconstruction of Sparse Signals via Nonconvex Minimization,”

IEEE Signal Processing Lett., 14, pp. 707-710, 2007.

[8] J.-C. Chin, L.-H. Hou, J.-C. Hou, C. Ma, N.S. Rao, M. Saxena, M. Shankar, Y. Yong, and

D.K.Y. Yau,”A Sensor-Cyber Network Testbed for Plume Detection, Identification,

and Tracking,” 6th International Symposium on Information Processing in Sensor

Networks, pp. 541-542, 2007.

Advances in Greedy Algorithms

324

[9] R. A. Dobbins, Atmospheric Motion and Air Pollution: An Introduction for Students of

Engineering and Science, John Wiley & Sons, 1979.

[10] D. L. Donoho, “Compressed Sensing,” IEEE Trans. Information Theory, 52, pp. 1289-1306, 2006.

[11] J. A. Farrell, S. Pang, and W. Li, “Plume Mapping via Hidden Markov Methods," IEEE

Trans. SMC-B, 33(6), pp. 850-863, 2003.

[12] E. B. Fox, J. W. Fisher, and A. S. Willsky, “Detection and Localization of Material

Releases with Sparse Sensor Configurations,” IEEE Trans. on Signal Processing, 55(5),

pp. 1886-1898, May 2007.

[13] P. S. Huggins, S. W. Zucker, “Greedy Basis Pursuit,”, IEEE Trans. Signal Processing,

55(7), pp. 3760-3772, July 2007.

[14] H. Ishida, T. Nakamoto, T. Moriizumi, T. Kikas, and J. Janata, “Plume-Tracking Robots:

A New Application of Chemical Sensors,”Biological Bulletin, 200, pp. 222-226, 2001.

[15] H. Ishida, G. Nakayama, T. Nakamoto, and T. Moriizumi, “ Controlling A Gas/Odor

Plume-Tracking Robot based on Transient Responses of Gas Sensors," IEEE Sensors

Journal, 5(3), pp. 537-545, 2005.

[16] P. Kathirgamanathan, R. McKibbin and R. I. McLachlan, “Source Release Rate

Estimation of Atmospheric Pollution from Non-Steady Point Source - Part 1: Source

at A Known Location,” Res. Lett. Inf. Math. Sci., 5, pp. 71-84, 2003.

[17] P. Kathirgamanathan, R. McKibbin and R. I. McLachlan, “Source Release Rate

Estimation of Atmospheric Pollution from Non-Steady Point Source - Part 2: Source

at An Unknown Location,” Res. Lett. Inf. Math. Sci., 5, pp. 85-118, 2003.

[18] C. Kennedy, H. Ericsson, and P. L. R. Wong, “Gaussian Plume Modeling of

Contaminant Transport,” Stoch. Environ. Res. Risk Assess, 20, pp. 119-125, 2005.

[19] J. Luo, “Low Complexity Maximum Likelihood Sequence Detection under High SNR,”

submitted to IEEE Trans. Information Theory, Sept. 2006.

[20] M. A. Mohamed, and P. Gader, “Generalized Hidden Markov Models - Part I:

Theoretical Frameworks”, IEEE Trans. on Fuzzy Systems, 8(1), pp. 67-81, 2000.

[21] M. A. Mohamed, and P. Gader, “Generalized Hidden Markov Models - Part II: Application

to Handwritten Word Recognition", IEEE Trans. on Fuzzy Systems, 8(1), pp. 82-94, 2000.

[22] A. Nehorai, B. Porat, and E. Paldi, “Detection and Localization of Vapor-Emitting

Sources,”IEEE Transactions on Signal Processing, 43(1), pp. 243-253, 1995.

[23] G. Nofsinger, and G. Cybenko, “Distributed Chemical Plume Process Detection,” IEEE

MILCOM, Atlantic City, NJ, USA, 2005.

[24] M. Ortner, and A. Nehorai, “A Sequential Detector for Biochemical Release in Realistic

Environments,” IEEE Transactions on Signal Processing, 55(8), pp. 4173-4182, 2007.

[25] L. R. Rabiner, “A Tutorial on Hidden Markov Models and Selected Applications in

Speech Recognition,” Proc. of the IEEE, 77(2), pp. 257-286, 1989.

[26] N. Rao, “Identification of Simple Product-Form Plumes Using Networks of Sensors With

Random Errors,” Proc. Int. Conf. on Information Fusion, Florence, Italy, July 2006.

[27] G. Schwartz, “Estimating the Dimension of a Model,” Annals of Statistics, vol.6, pp. 461-464, 1978.

[28] J. N. Seinfeld and S. N. Pandis,

Atmospheric Chemistry and Physics: From Air Pollution to

Climate Change, John Wiley & Sons, New Jersey, 1997.

[29] R. Tibshirani, “Regression Shrinkage and Selection via the LASSO," Journal Royal

Statistical Society B, 58, pp. 267-288, 1996.

[30] T. Zhao and A. Nehorai, ”Detecting and Estimating Biochemical Dispersion of A

Moving Source in A Semi-Infinite Medium,” IEEE Transactions on Signal Processing,

54(6), pp. 2213-2225, 2006.

[31] T. Zhao and A. Nehorai, “Distributed Sequential Bayesian Estimation of a Diffusive

Source in Wireless Sensor Networks,", IEEE Transactions on Signal Processing, 55(4),

pp. 1511-1524, 2007.

Greedy Type Bases in Banach Spaces

Witold Bednorz

Department of Mathematics, Warsaw Univeristy

Poland

1. Introduction

Let (X, &·&) be a (real) Banach space. We refer to [38] or [28] as some introduction to the

general theory of Banach spaces. Note that, as usual in the case, all the results we discuss

here remain valid for complex scalars with possibly different constants. Let I be a countable

set with possibly some ordering we refer to whenever considering convergence with respect

to elements of I (wich will be denoted by lim

i→∞

Definition 1 We say that countable system of vectors

is biorthogonal if for i, j ∈ I

we have

(1)

Such a general class of systems would be inconvenient to work with, therefore we require

biorthogonal systems to be aligned with the Banach space X we want to describe.

Definition 2 We say that system

is natural if the following conditions are satisfied:

(2)

(3)

(4)

Usually we assume also that

for all i ∈I, i.e. we normalize the system. Note that if

(4) holds then functionals

are uniquely determined by the set and thus

slightly abusing the convention we can speak about

being a biorthogonal system.

Observe that if assumptions (1)-(4) are verified, then each

is uniquely determined

by the values

and moreover

for every

Clearly the concept of biorthogonal system is to express each

as the series

convergent to x. If such expansion exists for all then we work in in

the usual Schauder basis setting.

Research is partially supported by the Foundation for Polish Science: Grant NP-37

Advances in Greedy Algorithms

326

Definition 3 A natural system

is said to be Schauder basis if I = N and for any the

series

()

ii i

∞

∑

x is convergent.

However in this chapter we proceed in a slightly more general environment and do not

require neither convergence of

()

ii i

∈

∑

x nor fix a particular order on I. Obviously still the

idea is to approximate any

by linear combinations of basis elements and therefore

for any and

we define

(5)

whenever this makes sense. In particular it is well defined for any finite J. It suggests that for

each m = 0, 1, 2, … we can consider the space of m-term approximations. Namely we denote

the collection of all elements of X which can be expressed as linear combinations of

m elements of

i.e.:

Let us observe that the space

is not linear since the sum of two elements from

generally in Σ

not in Σ

. For and for m = 0, 1, 2, … we define its best m-term

approximation error (with respect to

)

Commonly the system

is clear from the context and hence we can suppress it form the

above notation. Observe that from (4) we acknowledge that for each

we have

There is a natural question one may ask, what has to be assumed for

the best m-term approximation to exist, i.e. that there exists some

such that

The question of existence of the best m-term approximation for a given

natural system was discussed even in a more general setting in [4]. A detailed study in our

context can be found in [39] from which we quote the following result:

Theorem 1 Let be a natural biorthogonal system in X. Assume that there exists a

subspace

such that

1. Y is norming i.e. for all

2. for every we have lim

i→∞

y(e

) = 0.

Then for each and m = 0, 1, 2, … there exists such that

The obvious candidate for being the norming subspace of X* is

Later we will show that this is the case of unconditional bases.

The idea of an approximation algorithm is that we construct a sequence of maps T

: X →X,

m = 0, 1, 2, … such that for each

, we have that The fundamental

property which any admissible algorithm (T

)

m≥0

should verify is that the error we make is

comparable with the approximation error, namely

(6)

Greedy Type Bases in Banach Spaces

327

where C is an absolute constant. The potentially simplest approach is to use projection of the

type (5). We will show later that in the unconditional setting for each m,

there exists

projection P

which has the minimal approximation error, namely

Among all the possible projections, one choice seems to be the most natural: we take a

projection with the largest possible coefficients, that means we denote

where the set is chosen in such a way that

whenever j ∈ J and k ∉ J. The collection of such , i.e. will be called the Greedy

Algorithm.

Clearly

, m = 0, 1, 2, … have some surprising features which one should keep in mind,

when working with this type of approximation (cf. [40]):

1. It may happen that for some x and m the element

(i.e. the set J) is not uniquely

determined by the previous conditions. In such case we pick any of them.

2. The operator is not linear (even if appropriate sets are uniquely defined).

3. The operator

is discontinuous. To see it it suffices to fix such that

We define two sequences of vectors

Clearly both y

and z

converge to but

and

4. Following the previous example we learn that is continuous at the point if

and only if the set J used in the definition of

is uniquely defined.

5. If I = N then there is a simple trick to define

uniquely, namely given we

define greedy ordering as the map F : N → N such that

and

so that if j < k then either

and F(j)

< F(k). With this notation the mth greedy approximation of x equals

Advances in Greedy Algorithms

328

As announced we consider the greedy algorithm acceptable if it verifies (6). We formalize

the idea in the following definitions:

Definition 4 A natural biorthogonal system

is called a greedy basis if there exists a constant C

such that for all

and m = 0, 1, 2, … we have

The smallest constant C will be called the greedy constant of .

Definition 5 A natural biorthogonal system

is called quasi-greedy if for every the norm

limit

exists (and equals x).

Clearly every greedy basis is quasi-greedy. We remark that those concepts were formall

defined in [26] though implicit in earlier works of Temlyakov [30]-[33]. Throughout the

chapter we study various properties of greedy and quasi greedy bases. Toward this goal let

us introduce the following notation:

2. Unconditional bases

One of the most fruitful concepts in the Banach space theory concerns the unconditionality

of systems. The principal idea of the approach is that we require the space to have a lot of

symmetry which we hope to provide a number of useful properties. We refer to [37],[38] as

some introductory feedback to this item.

Definition 6 A biorthogonal system

is unconditional if there exists a constant K

such for all and any finite we have have The smallest such

constant K will be called unconditional constant.

Remark 1 Note that the above definition is equivalent to requiring that

for all

(not necessarily finite)

Sometimes we refer to a stronger property which is called symmetry.

Definition 7 An an unconditional system is symmetric if there exists a constant U

such for all

, any permutation and random signs we have

Greedy Type Bases in Banach Spaces

329

The smallest such constant U will be called symmetric constant.

Usually in the sequel we will assume that the unconditional system has the unconditional

constant equal to 1. This is not a significant restriction since given unconditional system

in X one can introduce a new norm

By the classical extreme point argument one can check that this is an equivalent norm on X,

more precisely

for and has unconditional constant 1 in

In the classical Banach space theory a lot of attention has been paid to

understand some features of spaces which admits the unconditional basis. We quote from

[1] a property we have announced in the introduction.

Proposition 1 Let be an unconditional basis for X (with constant K). Then

verifies that

for all

Proof. Let

. Since it follows immediately that

For the other inequality, pick

(from unit sphere in X*) so that

Then for each finite J we have

Now we let J tend to I and use that if

■

Therefore according to Theorem 1 the optimal m-term approximation for unconditional

system exists, i.e. is attained at some y ∈ . We remark that there are a lot of

classical spaces which does not admit any unconditional basis and even (e.g. C[0, 1] see [1])

cannot be embedded into a Banach space with such a structure.

In the greedy approximation theory we consider the class of unconditional bases as the fine

class we usually tend to search for the optimal algorithm (see [14]). The reason is that for

unconditional bases for a given the best m-term approximation must be attained at

some projection

Proposition 2 Let

be a natural biorthogonal system with unconditional constant 1.

Then for each

and each m = 0, 1, 2, … there exists a subset of cardinality m such

that

Proof. Let us fix m and be the best m-term

approximation i.e.

(the existence is guaranteed by Proposition 1). Note that

which completes the proof. ■

Advances in Greedy Algorithms

330

We turn to show that for unconditional systems

and are comparable. The result we

quote from [35] but for concrete systems (see [32]) the answer was known before.

Theorem 2 If is a natural biorthogonal system with unconditional constant 1, then

Proof. We have shown in Proposition 2 that we can take the best m-term approximation of x

Clearly for some . In order to estimate

we write

so using 1-unconditionality we obtain

Note that m.

This implies that

Thus

estimating c from the second inequality and substituting it into the first we get

Consequently

To show the converse inequality use the following result:

Lemma 1 For each m there exists disjoint sets J

and J

with such that

Proof. If

the claim is obvious. Otherwise take sets J

and J

with such

that

For simplicity write

With this notation we have This implies

Thus we have to replace J

by any set of proper cardinality which

contains J

and is disjoint with J

■