Bednorz W. (ed.) Advances in Greedy Algorithms

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

Greedy Type Bases in Banach Spaces

351

Thus using the Schwartz inequality and (40) we get

where we applied the following inequali

Consequently

■

Remark 6 If we assume only that

then mimicking the proof of Lemma 5 we obtain respectively

Remark 7 If

, where 1 < p < 2 or p > 2 then respectively (39) or (40) holds true. Thus

each greedy basis B such that , where p > 1, p ≠ 2, is Bessel or Riesz basis.

Furthermore for all p > 1, if the condition from Remark 6 is verified.

Lemma 6 Let

be a sequence of independent Rademacher variables and a

, a

i,j

∈ R, i, j ∈ N.

We have

Proof. The first equality is classical and easy so we only prove the second one. If

then there is nothing to prove, otherwise we have

where we have used the inequality

■

Lemma 7 Let are respectively greedy and unconditional basis for X. Let

and let K’ be the unconditionality constant for B’. If B is

Riesz or Bessel basis, then

where c is a certain constant (not depending on n).

Advances in Greedy Algorithms

352

Proof. Fix i ≥ 1. By the unconditionality of B’ and B and the Bessel property of B we have

Thus due to Lemma 6 we obtain

and hence

Now fix l ≥ 1. Due to the Riesz property of B and the unconditionality of B’ and B we obtain

If we take

then by Lemma 6 we get

It proves that

■

Remark 8 If we assume only that then

applying Remark 6 in the above proof (instead of Riesz or Bessel property) we obtain

for some universal constant c < ∞.

8.3 Proof of main result

Proof of Theorem 1. Fix n ≥ 1,  > 0. First we assume that < ∞. The definition of

implies that there exists x ∈ F

such that

Greedy Type Bases in Banach Spaces

353

Observe that

does not depend on the basis B renumeration, so we can

and we will assume that

Since F is aligned to B, whenever

we have

where u is a universal constant. Consequently

It proves that denoting the cube

is contained in F

. Applying the triangle inequality we obtain

Thus due to the unconditionality we get

hence

(41)

Fix

be a sequence of independent Rademacher variables. For simplicity

we denote

and consequently we have

Observe that

and thus for

m = 0, 1, 2, …. By definition

and

therefore

Advances in Greedy Algorithms

354

Furthermore, the unconditionality implies

thus

(42)

Again using the unconditionality and

we get

(43)

Now we apply Lemma 1 in the case of and derive that

Observe that hence by (42) and (43) we

have

The Schwartz inequality gives

Applying the inequality Lemma 6 and Lemma 7, we get

Greedy Type Bases in Banach Spaces

355

Thus

Taking m = k - τ , and using (41) we get

We can find suitable τ such that Since  > 0 is arbitrary we obtain

where This completes the proof when

In the case of

given M < 1 we can find x such that

Mimicking the previous argument we prove that

Since M is arbitrary, it completes the proof in the case of

■

Proof of Corollary 1. Obviously if X is L

space, then B is Riesz (for p ≥ 2) or Bessel (for 1 ≤ p ≤ 2)

basis. Moreover since

(see Section 2 in [9]), the basis B satisfies the Δ

condition

and thus we can apply Theorem 16. Assume that

That

means for every  > 0 there exists N() ∈N such that

Thus for n > N() + τ we have

Observe that

where c is a universal constant (which

depends on , β, τ only). Theorem 16 implies that

Advances in Greedy Algorithms

356

which is impossible since

■

Remark 9 Using Remark 8 instead of Lemma 7 in the proof of Theorem 16 and then mimicking the

argument from Corollary 1 (but for general Banach spaces and greedy basis B such that

) we get Theorem 15.

Remark 10 Results of [9] do not exclude the possibility that for some other unconditional basis B we

have It was conjectured in [40] that it is impossible.

9. References

[1] Albiac, F. and Kalton, N.J. (2005) Topics in Banach Space Theory. Graduate Texts in

Mathematics Springer

[2] Albiac, F. and Wojtaszczyk, P. (2006) Characterization of 1-greedy bases. J. Approx. Theory

138, 65-86.

[3] Arvanitakis, D. and Alexander, D. (2006) Weakly null sequences with an unconditional

subsequence. Proc. Amer. Soc. 134, 67-74.

[4] Baishanski, B. (1983) Approximation by polynomials of given length, Illinois J. Math 27,

449-458.

[5] Bechler, P. DeVore, R. Kamont, A. Petrova, G. (2007) Greedy Wavelet Projections are

Bounded on BV . Trans. Amer. Math.

[6] Bednorz, W. (2008) Greedy Bases Are Best for m-term approximation. J. Approx. Theory

(soon)

[7] Cohen, A. DeVore, R. Perushev, P. and Xh, H. (1999) Nonlinear approximation and the

space BV (R

), Amer. J. Math. 121, 587-629.

[8] Cordoba, A. and Fernandez, P. (1998) Convergence and divergence of decreasing

rearranged Fourier series, SIAM J Math Anal, 29, 5, 1129-1139.

[9] DeVore, R., Petrova, G. and Temlyakov V. (2003). Best basis selection for approximation

in L

. J. of FoCM 3, pp. 161-185.

[10] Dilworth, S.J, Kalton N.J., Kutzarova, D. (2003) On the existence of almost greedy

Banach spaces. 159, No 1., 67-101.

[11] Dilworth, S.J, Kalton N.J., Kutzarova, D. and Temlyakov (2001) V.S. The thresholding

greedy algorithm, greedy bases and duality. IMI-Preprints

[12] Dilworth, S.J. and Mitra, D. (2001) A conditional quasi-greedy basis of l

. Studia Math.

144 95-100.

[13] Dilworth, S.J. Odell, E. Schlumprecht, Th and Zsak, A. (2008) Partial Unconditionality,

Preprint.

[14] Donoho, D. (1993) Unconditional bases are optimal for data compression and for

statistical estimation. Appl. Comput. Harmon. Anal. 1 100-115.

[15] Donoho, D. L. (1996) Unconditional Bases and Bit-Level Compression. Appl. Comp.

Harm. Anal. 3, 388-392.

[16] Garrios, G, Hernandez, E. and Martell, J.M. (2008) Wavelets, Orlicz Spaces and Greedy

Bases. App. Comput. Harmon. Anal. 70-93.

[17] Gowers, W.T. (1996) A new dichotomy for Banach spaces, Geom. Funct. Anal. 6, 1083-

1093.

Greedy Type Bases in Banach Spaces

357

[18] Gowers, W.T, and Maurey, B. (1993) The unconditional basic sequence problem. J. Amer.

Math. Soc. 6, 851-874.

[19] Gowers, W.T. (1997) Banach spaces with small spaces of operators. Math. Ann. 307, 543-

568.

[20] Johnson, W.B. Maurey, B. Schechtman and G, Tzafriri, L. (1979) Symmetric structures in

Banach spaces, Mem. Amer. Math. Soc.

[21] Kadec, M.I. and Pelczynski, A. (1962) Bases lacunary sequences and complemented

subspaces in the spaces L

, Studia Math. 21 661-676.

[22] Kalton, N.J. Leranoz, C. and Wojtaszczyk, P. (1990) Uniqueness of unconditional bases

in quasi-Banach spaces with applications to Hardy spaces, Israel Math. J. 72, 299-

311.

[23] Kamont, A. (2001) General Haar systems and greedy approximation. Studia Math. 145,

165-184.

[24] Kashin, B.S. (1985). Approximation properties of complete orthonormal systems.

(Russian) Studies in the theory of functions of several real variables and the approximation

of functions. Trudy Mat. Inst. Steklov. 172, 187-191.

[25] Komorowski, R.A. and Tomczak-Jeagerman, N. (1995) Banach spaces without local

unconditional structure. Israel J. Math. 89, 205-226.

[26] Konyagin, S.V. and Temlyakov, V.N. (1999) A Remark on Greedy Approximation in

Banach Spaces. East J. Approx. 5 1-15.

[27] Konyagin, S.V. and Temlyakov, V.N. (2002) Greedy approximation with regard to bases

and general minimal systems. Industrial Math. Institute

[28] Lindenstrauss, J. and Tzafriri, L. (1977) Classical Banach Spaces I,II. Classics in

Mathematics, Springer, Berlin.

[29] Oswald, P. (2001) Greedy algorithms and best m-term approximation with respect to

biorthogonal systems. J.Fourier Anal. Appl., 325-341.

[30] Temlyakov, V.N. (1998) Greedy algorithm and m-term trigonometric approximation,

Constr. Approx., 569-587.

[31] Temlyakov, V.N. 1998) Greedy algorithm and m-term trigonometric approximation.

Adv. Comput. Math. 8, 249-265

[32] Temlyakov, V.N. (1998) Non-linear m-term approximation with regard to multivariate

Haar system, Esat J. Approx, 4, 87-106.

[33] Temlyakov, V.N. 1998) Best m-term Approximation and Greedy Algorithms Adv.

Comput. Math. 249-265.

[34] Temlyakov, V.N. (2002) Nonlinear approximation with regard to bases. Approximation

Theory, X 373-402, Vanderbilt University Press, Nashville, TN.

[35] Wojtaszczyk, P. (2000) Greedy algorithm for general biorthogonal systems, J. Approx.

Theory 107, 293-314

[36] Wojtaszczyk, P. Projections and nonlinear approximation in the space BV (R

), Proc.

London Math. Soc.

[37] Wojtaszczyk, P. (1997) A Mathematical Introduction to Wavelets, London Math. Soc.

Student Texts, Cambridge University Press, UK.

[38] Wojtaszczyk, P. (1996) Banach Spaces for Analysts, Cambridge studies in advanced

mathematics, 25, Cambridge University Press, UK.

[39] Wojtaszczyk, P. (2002) Existence of best m-term approximation, Functiones et

Approximatio 30, 127-133.

Advances in Greedy Algorithms

358

[40] Wojtaszczyk, P. (2002). Greedy type bases in Banach spaces, Constructive Theory of

Function Theory, Varna 2002 136-156, Darba, Sofia

[41] Wojtaszczyk, P. (2003) Projections and nonlinear approximation in the space BV (R

Proc. London Math. Soc., 87 417-497.

[42] Wojtaszczyk, P. (2006) Greediness of the Haar system in rearrangement spaces Banach

Center Publications: Approximation and Probability, 385-395, Warsaw.

Hardware-oriented Ant Colony Optimization

Considering Intensification and Diversification

Masaya Yoshikawa

Meijo University

Japan

1. Introduction

Swarm intelligence is the technological modeling of behaviors of social insects, such as the

ant or the honeybee. Although each element comprising swarm intelligence is simple, high

grade intelligence emerges when the elements gather to form a swarm. Ant Colony

Optimization (Dorigo, M, et al., 1997), which is called ACO, is one of the swarm intelligence

and has been attracting much attention recently. The ACO represents a general name of the

algorithm inspired by feeding behavior of ants. It has been applied to various combinatorial

optimization problems (Ramkumar, A.S. et al., 2006), including the travelling salesman

problem (TSP), the floorplanning problem (Luo, R., et al., 2007) and the scheduling problem

(Sankar, S.S., et al., 2005). The basic model of the ACO is the ant system (AS) that was

proposed by Dorigo et al. (1996), and many ACOs applied to TSP are based on the AS.

However, these ACOs require a lot of calculation time, because the optimization process is

based on repetitive searches by plural numbers of ants.

In this chapter, a novel hardware-oriented ACO (H-ACO) is proposed to achieve high-speed

optimization based on mechanism of ACO algorithm. The characteristics of the H-ACO is as

follows: (1) all calculations can be performed with only addition, subtraction, and shift

operation, instead of the floating point arithmetic and power calculation which are adopted

in conventional ACO; (2) a new technique using Look-Up-Table (LUT) is introduced; and (3)

in addition to upper and lower limits, benchmarks are set to the pheromone amount.

Experiments using benchmark data prove effectiveness of the proposed algorithm.

The organization of this chapter is as follows: Section 2 describes the search mechanism of

ACO and briefly surveys the ACO research in terms of the computational time. Section 3

explains H-ACO. Section 4 reports the results of computer simulations applied to travelling

salesman problem. Section 5 summarizes the chapter.

2. Preliminaries

2.1 Ant colony optimization

Ant Colony System is one of the expansion algorithm of AS, and it shows better capability

than genetic algorithm and simulated annealing when applying to TSP. Therefore, we adopt

Ant Colony System as a base algorithm and the target problem is TSP. Hereafter, ACO

indicates Ant Colony System.

Advances in Greedy Algorithms

360

The search mechanism of ACO utilizes the static evaluation value and the dynamic one. The

static evaluation value called heuristic value is peculiar information of the target problem,

and the dynamic evaluation value is pheromone amount. Usually, a reciprocal number of

the distance is adopted as the heuristic value, when ACO is applied to TSP. Specifically, ant

k in city i selects the move to city j according to probability p

and it is defined as follows.

(1)

Where,

(i,j) is a pheromone value between city i and city j,

(i,j) is a reciprocal number of

the distance between city i and city j,

is a parameter which controls the balance between

static evaluation value and dynamic one, and n

is a set of un-visit cities.

On the other hand, a pheromone amount on each route is calculated by using two

pheromone update rules. One is a local update rule and the other is a global update rule.

The local update rule is applied to the route which is selected by equation (1), and it is

defined as follows.

(2)

Where,

is a decay parameter in the local update rule,

0 is initial value of pheromone. Thus,

the local update rule adds the pheromone to the selected route when the ant moves. The global

update rule adds pheromone to the best tour (the completed route) of all tours. The best tour

usually indicates the shortest tour. The global update rule is defined as follows.

(3)

Where, T

is the best tour, and L

is the total distance of the best tour.

2.2 Related work

Examples of dedicated hardware for ACO are found by Haibin et al. (2007), Nakano et al.

(2006), and others. Haibin et al. (2007) proposed the hardware architecture that combines

genetic algorithm and ACO, and they showed the validity of the combined architecture.

Nakano et al. (2006) implemented the partial function of ACO on FPGA (Filed

Programmable Gate Array), and they demonstrated more high-speed than software

processing. The authors also proposed the dedicated hardware of ACO (Yoshikawa, M., et

al., 2007). However, the developed hardware was based on ordinary ACO algorithm, and

adopted floating point arithmetic as calculation of pheromone update rules.

Regarding other meta-heuristic algorithm, the dedicated hardware approach to reduce

calculation time are reported by Scotte et al. (1995), Imai at al. (2002), and Frye et al.(1991).

Scott et al. (1995) developed a hardware-based GA and demonstrated its superiority to

software in speed and solution quality. Imai et al. (2002) proposed a processor element

constituting parallel GA, and achieved the parallelism due to the number effect. Frye et al.

(1991) developed the dedicated hardware for neural network using analog device.