RANDOMIZED U N B I A S E D DESIGN OF REGRESSION EXPERIMENTS ON FUNCTIONALS IN A H I L B E R T SPACE

UDC 5!9.21

E. V, Sedunov and A. V. Lipin

The paper examines optimal design of experiments for estimating a functional dependence from the results o f noisy observations of some functionals of an unobservable function.

Ermakov's randomized experimental design theory uses the following procedure [1]. Given is a set ~" of functions which are continuous on a compact topological space ~; # is a finite Borel measure on ;~, ,7 is an unknown function, rt ~ ~r. Given the measurements (which contain some errors) of the values of the function ,7 in specially chosen points of 36 , it is required to construct in a given finite-dimensional subspace 9-0 ~ ~ an estimator ~ which is unbiased relative to the best approximation (in the metric L2( ~ , #)) of the function ~ in ~'0. With scanty a priori information about r/(e.g., dim g ' = ~ ) , a finite collection of experimental points (a deterministic design) cannot be a solution of this unbiased experimental design problem and we need to resort to random choice (a randomized design). In this paper, we propose some techniques for construction of randomized unbiased procedures for a more general measurement scheme, when r/ is unobservable and we can only make measurements on some set of linear functionals of ,7. The results extend the theory of randomized unbiased experimental design to a wide class of important applied problems with infinite-dimensional design domains, e.g., many inverse problems of mathematical physics. In view of the numerous applications of experimental design for problems with an infinite-dimensional domain, the issue is certainly topical, and its particular aspects have been previously considered in [2-5]. In summary, we stress that the contribution of our study to the existing body of research on regression experiment design is determined by two factors: first, we extend the traditional randomized theory to measurement schemes on functionals in a Hilbert space; second, we generalize the theory of experimental design in functional spaces to problems with scanty a priori information about the regression function. 1. STATEMENT OF T H E PROBLEM Let ~ be a real separable space with the scalar product (., .) and the corresponding norm I{" {I; '7 an unknown element of 3 , which has to be estimated from experimental results; '-// a given bounded Borel subset (design domain) in the completion ~4e of the space J{ . The elements of ~ are the functionals of the Hilbert space ~ on which ,7 is measured in N observations:

yN (h N, (oN) = (]], hN> .2U N (fiN, CON),

(1.1)

N where h u := (hi . . . . . h~:)-r C ~ N = X '/s Q1, hU> : = ((aq, hi> . . . . . (~, hu)) r ; co:: : = (col. . . . . CON)v is an element of the i N

probability space (f~,(~, v) n = X (f2, ~d, ~:); yN(hn, wN) := (y(h 1, w1) ..... Y(hN, WN))W is the vector of measurement 1

results; eN(h N, wN) := (e(h 1, w1) ..... e(hN, WN))r is the vector of random errors with the properties E~e (h, co) = 0 Vh E ~ ; sup o ~ (h) < oo, tzE~

a~ (h) : = E~e 2 (h, co), where E~ is the expectation by the measure u. Translated from Kibernetika, No. 2, pp. 58-66, March-April, 1991. Original article submitted October 25, 1989. 234

0011-4235/91/2702-0234512.50

9

Plenum Publishing Corporation

A randomized experimental design with the scheme (1.1) is an arbitrary probability measure ~ on the Borel aalgebra 9ff of subsets of the set q2 ~ , corresponding to the experimental realization of the series h N. The estimator ~ of the unknown element t/E ,~ is constructed in a fixed finite-dimensional subspace 3~o ~ , dim ff'~o= rap, using the family of bounded linear operators R s -+ ~ 0 , i.e., ^

N

N

= Shay (h , oN).

(1.2)

The tuple ~r = (~(dhN), ShN) that satisfies the unbiasedness condition Erl = Po~q Vq E 3~,

(1.3)

where E = E~E~oN is the complete mathematical expectation, Po : .3~ ~ .~o is the orthogonal projector, will be called linear randomized unbiased (LRU) procedure for estimation of ,7 in ~ . The set o f such procedures will be denoted by HLRU. A particular case of L R U estimation procedures are linear deterministic unbiased (LDU) procedures [6]. For a fixed estimation space ~ o , condition (1.3) is necessary and sufficient for minimizing the systematic error a(r) := IJ~ -- E~ II ~- The choice of the procedures ~- in the set HLRv is naturally required to satisfy the condition of minimum random estimation error of r/, which is usually characterized by some monotone functional r of the covariance operator D[~] = E{(//-- E//) | (~ -- E//)}, D[~]: ~ 0 ~ Jgo, of the estimator/1. In specific problems, we should bear in mind one features of L R U estimation procedures compared with LDU procedures: the covariance operator D[//] depends not only on the procedure ~r but also on the unknown element ~7. Indeed, for the element (i, j) of the matrix of the operator D[~] in an arbitrary orthonormal basis {fi}i=l m0 in the space o~o we have ~,

[D (~;

tx [1 .....

,-x

[mo)]ij : E~ {/~0~0i EoO/} (aq)

+(D[ShNS N(h g

N

and in the LDU procedure the algebraic sum of the first and the third terms vanishes, so that there is no dependence on r/. This uncertainty can be eliminated by local, Bayesian, or minimax approaches, which make it possible to pass from the criterion r ~/) to the criterion r in the problem ~*=Arg

inf 0(~). n~rILRU

(1.4)

2. CONVOLVING MEASURES AND REGULAR SPACES We need some auxiliary definitions and propositions for the construction of L R U procedures and analysis of their properties. Definition 1. We say that the pair ( ~ , ~0) can be convolved on the set c/L, if there exists a finite Borel measure )~ on ~L (which in what follows is called a convolving measure) such that

(,, u> ~ (du) = (f, ,). f E 5~. , E ~o.

(2.1)

U

Proposition I. Let ~ be a compact topological space,/, a finite Borel measure on :~, f f ~ L 2 (~, ~t) 6 C (~), where C ( ~ ) is the space of continuous functions on 3~ ; the metric in the space ,~ is induced from L2(:~, #), h z E 9'~0 c ~,~ is the functional "measurement at the point z,"

{h,h~)=h(z),

hE3go, zE~s

The design domain c/L is the set

://~ (3%) : = {h~ : z E ~}. 235

Define the continuous function

x : ~---~q~(~0)

, r(z) := h,., and the measure A~ = r(/z):

~.~(V) := ~ (~:-~ (V)), where V is a Borel subset o f q~, (No) 9 T h e n for any .~o ~ ~ the measure ;ke convolves the pair Proof. For any ~b ~ ~,o and f ~ oag , we have

(2.2)

(3~, ~o) on % (~o).

: = :o + :,, :oE ~o, :~ ~- .,% ~d (:,,) = ~ (:o, hz) @, hz) F~(dz)

=

~

<,, .> ke (du)

~'e(WO)

=

f

(:, u) ( , , . ) ~o(d.).

~(Wo)

Proposition 2. If the set

contains some orthogonal basis ~ = {e~ ..... emo) of the subspace

o~o ~ . ~ , then

the measure ITZo

i=l

where 8~i is the Dirac measure, convolves the pair ( ~ , No) Proof. For arbitrary : E .~, ~bC .3~ 9 we have

.I~' u) (% u) ~,~ (du) =

on 2Z.

mo

).~ 11e, Ii-~ (/, e~> ( , , e~>

(2.3)

t~ o

= (/, ~ (*, 11e~ IF-"ei)!1 e~ It-~ e~) = (:, % i=1

C O R O L L A R Y . For any r > 0 and any finite-dimensional subspace .Z/go~ Jte the pair ( ~ , ~o) can be convolved on the ball ~L~e,r of radius r in the Hilbert space Je-- and each orthogonal basis $ = {% ..... emo} of the subspace ~ o contained in qd~e,r generates by formula (2.3) a conv olving measure ~.~r. Proo]. Any orthogonal basis of .:/go, with norms of elements not exceeding r satisfies the condition of Proposition 2. Proposition 3. Let o@~,obe a Hilbert space, di m ~ o ~ m o , ~}~o~ L~(2~,/~) (I C(~), ~ an arbitrary operator that isometrically maps ~ff/~o on .,~o ; c an arbitrary constant such that norm of the embedding

id2,= (~0): (~0,

~z,= (a~0) ~ c <~ oo, where •

(~o)

is the

II'IIL,<~e,~))~ (~o, II'llc<~e)).

If ~e is a convolving measure of form (2.2) for pair (~}~o,/~o) on '/Le (a~o), then for any space a~o ~ ,~ the measure ~'J,c,

c2 ~. [C ^_ (2.4) where V is a Borel subset o f ~ ' o , r

'/t~, r).

236

, convolves the pair (,~, a~o) on the ball '/t~o,r (and therefore also on the ball

Proof is by checking condition (2.1):

=

<~o f, .> <,, .> a~,~(a.)

! ~'~'o. r =

In Proposition 3, the domain ~ ' o , r

I (f, U} (~, .} Z~,c (du). ~'ff-t'o,r m a y be replaced with any set U that includes

2 ~ ' , c :-----supp ~N,c --=

r

•

~-~ (~ (~o)). Proposition 4. Let N ~ L~ (~, IX), ~ (~) < c~, ~zx = { a (x) E L ~ (~, Ix) : a (x) E A Vx E ~ (rood ~_)}, A = [Co, C~], C o 0
2t-4~:=/

/~--

If J~o ~ L~ (~, IX), then the pair (J~, ~ ) f o r m (2.4), where min {1Co 1,

Cx}, •

can be convolved on 4 ~

~ : ~o--* J~o is an isometric operator, ,~,:

with respect to the m e a s u r e

L (~, IX~)N C (~), c / > xe.~ (,~o), r =

(No) is the norm of the embedding de,r (o~o) : (No,

ro/•

~],c of the (,~o), ro

II'llc~,~) ~, (o%, I1"IIL~r

Proof. Since dim ~ < ce, the norms of the spaces L 2 ( ~ , #) and L~176 , #) induced on ~ o are equivalent and of the e m b e d d i n g id2,cr ) is finite. For an arbitrary hEa~o, IIh IiL~e~,~~< r, we have

the norm ~2,cr

i.e., h E ~4[c0.cd . Now, h = P~h E P ~ t c o , e , ] = 4[Co,Ca and q.t~o,r ~ 4[c,,cd. It remains to apply Proposition 3. Proposition 5. U n d e r the conditions of Proposition 4, the pair ( ~ , 5~go) can be c o n v o l v e d on 4 a , . A = [Co, C1] , C o < 0 < C 1, with respect to the measure ~ " o f the f o r m (2.3), where $ = {% ..... emo } is an orthogonal basis in N0, contained in ,,4A, ei = (ro/llhi [IL=(Z.~)h~, i = I ..... mo, r o = min{ICol, C1}, {hi)i=l m0 is an a r b i t r a r y orthogonaI basis in ~ o . Proof. Clearly, I1e~ IlL~t~.g) = ro, and therefore e~ E t/~t--r,.r,] ~ ~ttc~.cd. Thus, ei=P~ei E P~d[eo,Cd = q'L[Co,C,]. It remains to a p p l y Proposition 2. Thus, assume that the measure A convolves the pair ( N , o~o) on ~ . An analog of the notion of regular basis is p r o v i d e d by the following definition. Definition 2. The subspace J~o ~ N is called regular with respect to the measure A if

4 o c 4 , ~ (40) > o =~/to ~ fi Ygo = {0}, where 4 ~ : = {h E ~ : ( h , u }

(2.5)

= 0 VuE40}.

L E M M A 1. The subspace No ~ .,~ is regular with respect to the measure ), if and only if

x {f l} = o vf E y&\{o},

(2.6)

where f• :---- {h E.~~ : (h,/r = 0}. Proof. Let d~/?o be a subspace in o~ regular with respect to the measure ), and assume that there exists an element f E .~o such that f # 0 and ~{f• > 0. Setting "/to = f• N 4 , we obtain L (C/Lo)= ~{f• > 0, and f E .,~o N 4 ~ , which contradicts the regularity condition (2.5) for ..~go. Conversely, assume that p r o p e r t y (2.6) is satisfied and let the subset q~o c 4 be such that 3~(i4o) > 0 and 0 f E qgox [7 .,~o. By (2.6), ~{f• = 0 and by q/,o c f• we obtain )~(:4~ ) = 0. 237

R e g u l a r i t y of the subspace J t 0 0 ~ o ~ relative to the convolving measures ~e, ~ , using T h e o r e m 1. T H E O R E M 1. The subspace ,~o ~ oq~ is regular: a) with respect to the measure Ae (2.2) if and only if

(z E ~ : / (z) = o} = o

and )~,e

can be decided

W E 2r

b) with respect to the measure ~,~r (2.3) if and only if dim ffgo -- 1; c) with respect to the measure ~',~,c (2.4) if and only if ~ o is a regular subspace with respect to the measure ~e"

Proof. 1. Since supp Ae = c/Lo (~o), regularity of ~ o with respect to the measure ~e is equivalent by L e m m a 1 to the condition x~ ([ z Cl %~ (~o)} = o

vf E No\(O}.

(2.7)

Let [ E ~ o ~ { 0 } , u E [• N 2L~ (]/go). Then there exists z E ~ such that u = h~, and since u _L f, we have f(z) = (f, h,.) = (f, u) = 0. T h e r e f o r e (2.7) m a y be rewritten in the f o r m

;~ (h~ E ~ , (,~o): f (z) = o} = o

v/E ~ o \ ( O ) ,

which given (2.2) is equivalent to condition 1. 2. Let dim 3tg0 > 2, el, e 2 ~ ~. Since e~ • e I and therefore e 2 ~ el • and X~.((e2)) > 0 f r o m the definition of the measure 3.~, then using L e m m a 1 we conclude that 3ifo is irregular with respect to the measure X~r. Conversely, let d i m Jte~ = 1, ~ = {e}. F r o m the definition of &~r we have supp ~ , = {e}. If f is an arbitrary nonzero element of ~ o , then e $ f• and therefore ~ { f • = 0, whence by L e m m a 1 we obtain that .~o is regular with respect to ~.~. 3. The last assertion follows f r o m the fact that the regularity p r o p e r t y (2.6) is conserved under isometric transformations, homotheties, and multiplications by a constant (see (2.4)). 3. E X I S T E N C E AND R E A L I Z A T I O N OF L R U P R O C E D U R E S The unbiasedness condition (1.3) imposes certain constraints on the estimation space ~)~o in L D U and L R U procedures (see [6]). T h e r e f o r e , if ~ o is specified by the p r o b l e m , the existence of these procedures cannot be guaranteed. T H E O R E M 2. For the existence o f an L R U procedure it is sufficient that ~ o ~ Win 2/,

(3.1)

,,~o ~ Clue Win ~ .

(3.2)

and necessary that

9 Proof. Assume that (3.1) holds. Fix an orthonormal basis {fi}i=l m 0 m .~o . By (3.1), all its elements are contained

in ~ i n 2L a n d thus there exists a set {h 1..... hr} C ff.g, r _> m o, such that fi E LPin{h 1..... hr}, i C 1 ..... mo, i.e.,

fi = ~ aahj,

i = 1, .... mo.

/=1

Then for an a r b i t r a r y r / ~ ~

we have mo

r/z o

Pon = Y, (n,/~> fi = ~ i=l

238

i=1

~,J
As the linear estimation operator Sa~ : R ~ --~ ~]~o take the operator which has the m a t r i x (aij)i=l,j=lm0 ,r in the standard basis (Xj}i=l r of the space R r and in the basis (fi}i=l m0 of the space ~ 0 . Then E

A

oN~l ~- EoNShrY r = E oNShr (Yl . . . . , Yr)T

= Sa, fin, hi) . . . . . 0q, h~))r = Po~l, which proves the existence of an LDU procedure with design support elements h 1..... hr, which may be viewed as a particular case of an L R U procedure. Now let (((dhN), ShN) be an L R U procedure. Then from (1.3) we have

I ShN ('i~,hN) ~ (dhN) =

Po~l

qEN

for any r/ E ~ . From continuity considerations, the last equality is satisfied for any r/ E ~ . Therefore, the relationship ~l C ( C / ~ ~gin ~)-~ implies Pot/= 0, i.e., 77E ~ 0 ~. Hence (Clue ~in ~/~)• ~ ~ oT , which gives (3.2). Note that for the existence of an LDU procedure, conditions (3.1) are both sufficient and necessary [6]. The main technical difficulty in this problem is the realization of the chosen randomized measure ~. In what follows, the measure ~ corresponding to an L R U procedure will be chosen as absolutely continuous with respect to the measure AN, where )~ is some convolving measure on ~ . In this way, we can simulate ~ given the probability measure A/1[ A 11, e.g., using Neyman's method, although in some particular cases special simulation algorithms may be used. Simulation of probability measures of the form A/[[ A [1 does not involve special difficulties. Indeed, measures of the form ~,~/[]L~ ]l are trivially simulated as discrete measures, while the measures ~,~/[Ik~ tl and ,k],c/I I L~,c I[ are represented respectively as r(#)/11 # ]l and - ~ - I[ ~ -,o

ox

l(7),ll

o.,izat on t o oforo

to

of the measures # and/L and transfer of the samples by an appropriate mapping into the set c/~L. Simulation of the measure ),/][ ), 1! is similarly simple for many other examples of convolving measures ~. 4. LRU P R O C E D U R E S 7r(~

AND 7r(I) WITH ORDINARY LEAST S Q U A R E S AND

INTERPOLATION ESTIMATORS

Let N > m o. Take the ordinary least squares (OLS) method as the estimation technique, setting in (1.2)

f Is'ja vle N, it s; e N Sh N = S (hNOLS ,) : = /

is invertible, 0

(4.1)

otherwise 9

where the operator Jh N : .)~o'-->" I~N is defined by

J aNf: =( f, hN) = '>((f , hi) ..... (f, h~r ) "r , redo. The vector of the functionals h N E q,~N is chosen according to the randomized design ~( OLS

_-

) (dh")

( N - - mo)! det [J*hNJhN] ~]V (dh~V), N! [7, (~//)ff-m.

(4.2)

where A is some convolving measure for the pair ( 3 , 3o) on c/L . In what follows, we will need analogs of integral identities from [1].

239

LEMMA 2. 1. L e t {tpi)i=lmo and (r

m~ be two systems of elements in the subspace ffeo . Then

mo XN S det ([%, ~t]t,2v. . . . . [(P,,,,, ~hlhN)Z=~

(dhN)

NI (N - - mo)i det ((%, *z>,

(4.3)

.... (%~ '3)?=",[~, (l/)1 N-'', N

where [f. g]h~v: = E (f' h~> . /=1

2. L e t {fi}i=l m0 be an orthogonal basis in the subspace o~o ~ .,~;

% *E~.

Then for r, t E l,...,m o

'if., t.]~ ..... [h, L-,].,~, If,, %,~, [h, f.+,].,, ..... [h, Lo].~ , . .

, .

.

.

.

,

.

.

.

.

.

.

~ o

.,.

S det [ft--l' [1]h N ..... [f,--l' fr--1]h N' [fl--,, *]h N* [ft--l' fr+l]h N ..... [ft--l' fmo]h N X

[% f,]h N ..... [q), fr_l]hN, [(~, *]hN, [~, fr+t]hN ..... [% fro.JaN

[ft+1. h]hN .....

[ft+p fr--t]hN. [/~+I.

*]hN, [ff-H' :,+1]h ~ ..... [f~+,.

fmo],N

,Its,, f~ihN ..... [f~o' f.--~]."' [fm,, *]h N, [t~, f.+~hN ..... [:..~ fmo]hN NI[~,(~)IN_m ~ X Z/v(dh~V)=

( N - - too)!

(4.4)

[@, fr) (% [t), if =or=/=t' x [(,, ~)vc~,,~,) -- ~ (% f~) (r f~>, if r = t. l=1,

i=#r

Proof of identity (4.3) is similar to the proof of Lemma 5.1 in [1], and identity (4.4) trivially follows from (4.3) for ~ok := fk (k ~ r), ~or := r Ok := fk (k ~ t), Ct := ~o. Proposition 6. The measure ~(OLS)(dhN) defined in (4.2) is a probability measure. Proof is by verifying the normalization condition using the identity (4.3). Let us now formulate the main result of this section. THEOREM 3. The procedure r(~ = (((~ Sh N (OLS)) with ordinary least squares estimators ~(OLS) defined in (4.1) and (4.2) is an LRU procedure. For any r ~ ,~o, IIr II = 1, we have (D [~1(~

}] 15. ,) <~. S (P,~e~o ~1' h)2 ~"(dh) ez

+

a/d

o, (h)

-- 3" S p (h, h') < P=oo, h, .'> '~'dqd

(4.5)

• ~ (dh) 7, (dh3, where p(h, h') := Ew[~(h)e(h')], and the equality in (4.5) is attained if and only if the subspace ~ o is regular with respect to the convolving measure A and r/= r Proof. We start by checking the unbiasedness condition (1.3) applying Lemma 2: (~](OLS) fh) = S~N f

X ~( oLS ) (dh~.)=

.,~,(OLS). ,'LN, N ) , f D X ~~ y N v~

(N -- too)!

~' det ([[z. ft] ....

N t [~, (TZ)]N-=~ ~N

240

.... [[~, f~-~l, [f~, ~1], [f~,/~+t] ..... [f~, fm,l)~~ %N(dhg) mo

/=1 , i ~ k

= S (~1, h~, (/~h, h) ~, (dh) = (n, [h),

k E 1 : me

Inequality (4.5) is obtained using the Binet--Cauchy formula and the Cauchy--Bunyakovskii inequality, by an argument which is basically the same as in the proof of the corresponding inequality in [1]. A particular case of the procedure ~r(~ is supplied by the following corollary. COROLLARY. Let N =mo~ The procedure ~r(~) = (~(Z)(dh'~'), S ~ ) with interpolation estimators//(~), where

1 U [det Jhrn~] ~ ~m, (dh,n,), ~(I)(dhm~ = too--I

--1

9

Shrno = S(i)hm* :--= Jhmo' if [

(4.6)

Jhrn, is invertible,

(4.7)

0 otherwi se,

is an L R U procedure. For the variance (D[~(I)]r r Vr c o~0, 1]r H = 1, we have the bound (4.5), where the equality is achieved if and only if the subspace ~ o ~ ~ is regular with respect to the convolving measure ),. Procedures of the type 7r(~ and ~r(x) of course do not exhaust the entire class of L R U procedures. Varying the estimation operators ShN and the randomized designs ~(dhN), while oberving the unbiasedness condition (1.3), we can easily construct other examples of L R U procedures (see, e.g., [71). In this way, we can consider optimization of LRU procedures in the framework (1.4) not only by an appropriate choice of the design ((dh N) and the operator ShN (similarly to [8]) but also by a choice of the convolving measure A. 5. CHOICE OF CONVOLVING MEASURE IN PROCEDURES It(~

AND 7r(I)

In the previous section, we constructed L R U procedures ~r as a function of some convolving measure A. This measure may be treated as a free parameter, whose choice is left to the user in accordance with a given optJimality criterion q~(Tra)in problem (1.4). To solve this optimization problem, we need some auxiliary results. Definition 3. We say that the set '~ weakly majorizes the set ~ , if N

vhE~

N

HtER:hEt~.

Definition 4. A measurable subset ://o of the set q/ is called its section if: a) qdo weakly majorizes c/t; b) f o r h o , u o E q.L~ , w e h a v e h o = t u o ( t ~ R ) = > h o = u oEach section ~ o o f t h e s e t 2/. generates measurable mappings I10:2t-+2s ~ Rsuch that

IIx:c/Z--+l~,

l-loh___ho' I l l h = t '

if

h_=tho, hE~,ho6"7~o, tER ,

fi~=h0,

if

~=tho, acqZ, hoE%,tER.

rIlh=t,

~ ~ o:2g--+~t',~, 171 :

(5.1)

For h, h ~ 0, these mappings are well defined by condition b; the values of IIo and IZlo at zero (for 0 ~ 2[ and 0 ~ Y/~) are defined arbitrarily so that IIo0, l:Io0 ~ .7~o, and II10 and 1:I10 are set equal to zero. The mappings 1Io and lrIo will be called projections of the corresponding domains on the section .'~L0. THEOREM 4. Let A be a convolving measure for the pair (o~, a~o) on 2L; assume that the design domain, '~L weakly majorizes 2/ and in ~ there exists a section '~o such that the mapping rI1 : 3]L -+ R (5.1) is square summable by the measure )~. Then: 1) a measure A~ exists in "~ with a support in 2Lo, .

=

n

=

(5.2)

which convolves the pair (${, .~o); 241

2) the subspace ~ o ~ a~ is regular with respect to ~ if and only if it is regular with respect to Ao. Proof. 1. Under our assumptions, relationships (5.2) define finite Borel measures on ~ and ~ o , and for arbitrary f E ~ , ~ r E Jteo we have

II~h

'~/

= j' (f, ho) (r ho) Xo (dho). ~o 2. The second assertion follows from mutual absolute continuity of the measures ~ and ~'. By the experimental condition (1.1), a real measurable nonnegative function a2(h) is defined on the design domain 2 l . We associate to this function some subset 2/~, ~ 2/ by the following rule. For an arbitrary h ~ 2 / d e f i n e the function q~h : {rE R \ { o } : th EU} -,- R,

q'h (t) = o 2 (th)/t ~.

(5.3)

Assuming that the function ~oh achieves its minimum for any h and T h is the set of points t where this minimum is achieved, we take

2/~, -- {th : t E Th, h E ~}.

(5.4)

LEMMA 3. Let I be a convolving measure for the pair ( ~ , ~o) on ~ , of the set 2/,, c 2l. Then

S

A~ its projection on some section 2/0

S

,e

%

(5.5)

and the equality in (5.5) is achieved if and only if the measure i is concentrated in 2/~. Proof. By construction of the set q/a, (5.4),

(Drlah(IIlh) ~ qgYl.h(1) Vh E '~.

(5.6)

Using the obvious relationship (see (5.3))

'~,h(t)=s~Cph(st),

sER\,{O};

sh, sthE2/,

and the definition of the measure I p, we obtain

p (h) ~, (dh) = S cpa (1) ~, (dh) = S r176 ql ql

(1) L (dh)

= ~ ] H~h 12Cpn,n(H~h) k (dh) ~,~ ~ cpn.h(1) ~.' (dh) 'g q/ --'-- ~ r

(1) ~o (dho) = f p (ho) ~o (dho).

Since equality in (5.6) is achieved only for h E 2/,~, equality is achieved in the last relationship if and only if h is 1-a.e. contained in 2 / ~ .

242

COROLLARY. If the set % is separated from zero (i.e., h~,7/ inf [t h [I> 0), and the function O2(h): ~ ~ R+ is defined as above, then the real function ~ ~" S ~r=(h) ~, (dh), defined on the set of all measures ~ convolving the pair e., (a~, ~ , )

on ~ , achieves its m i n i m u m on the measure , ~ concentrated in ~

Proof. Separation of ell f r o m zero ensures the existence of a projection A~ of an arbitrary measure )~ on any section odo of the set ~o-" . It remains to apply L e m m a 3. The above leads to a natural definition of the subset ~ ' ~ od as a~'-optimal for ~ . Definition 5. We say that the design domain '/L strongly majorizes the s e t ~ if: a) ?Z weakly majorizes '2/; N

N

I'~

b) ~ ' h E ~ Z , ~ r

l..

The section qdo is called a strong major of ~ , if od0 strongly majorizes ~ . Strong majors of q.[ are obviously maximal elements by the strong majorization relation among the sections of ~ . If qL is closed, then the strong majors of eLL are identical with the sections of the set

'IZ,~ : = {h E 2L : th E qZ=e-l t l ~ I}. Note that if q.t is an open set, then in general the set c/L,, may be empty and we must satisfy ourselves' with the possibility of projection on sections near the "boundary." Proposition 7. Let the function a = be such that for any h E od the functions ~Oh(t) are strictly monotone decreasing for t > 0. If the set q~ contains at least one strong major, then there exists a a2-optima! subset ~ and %,,~ = 2/,., N 2t.

Proof is f r o m the definitions of the set U J" and strong major. The conditions of Proposition 7 in particular are satisfied if a2(h) = const for any h E ~ or a2(h) = c II h II ', < s < 2. For a~'(h) = c I1h 1[2 all the functions ~h (h ~ ~ ) are constant and therefore ~ e , = od. For d ( h ) = c II h II 8, s > 2, the set ~ , obviously consists of the elements of c/L closest to zero on each line through the zero (according to the accepted terminology, this set is naturally called a minor of 2L). T H E O R E M 5. Let r~ (I) be an L R U procedure constructed by the convolving measure A for the pair ( ~ , d~/o) on ~ , assume that the subspace ~(o is regular relative to the measure ), and the observations on different functionals are uncorrelated. If a a2-optimal set 9J~

exists for ~

and there exists a section c[Lo of the set ~ o , such that II 1 E L2(.Od, A),

then for the projection A~ of the measure ), on c~o we have

where ~ is an arbitrary monotone functional of the covariance operator D[//r(I)]. Proof. We will show that under the conditions of the theorem

~ o (h, h') < P~eon,J " h, h" > ;~ (dh) ~, (dh') = O.

(5.7)

For dim aago_ 2, regularity of ffgo with respect to the measure ;~ implies continuity of A and therefore also (5.7). Indeed, for any h ~ qs there exists f ~ 2No \{0} such that f _Lh and, by regularity, ;~({h}) _ 1(f• -- 0, whence ~({h}) = 0. If dim 3v~o = 1, then clearly o~o n r177= {0} and the integral in the left-hand side of (5.7) vanishes. Therefore, minimization of the monotone criterion r is equivalent under the conditions of the theorem to minimization of the expression (using (4.5) and regularity of ,~o,)

(D[~I(I)J~' ~) = ; (P~GYG~I' h)2L(dh) -}- S e= (h)L(dh). 9z

(5.8) 243

Since

.~e,,%,l, h>, = ~ II h II~, the first term in (5.8) is invariant under projection o f the measure ~ on sections o f the set nd;, and the second term by L e m m a 3 satisfies (5.5). In case of OLS estimation, regularity of the subspace 3~0 in itself is insufficient to achieve the equality in (4.5) (see T h e o r e m 3). T h e r e f o r e , in p r o c e d u r e s r(~ (as in procedures ~r(I) with irregular ~ o ) , we can only consider minimization of the u p p e r b o u n d in (4.5). T h e required changes in the f o r m u l a t i o n o f T h e o r e m 5 are obvious. In conclusion o f this section note that, as is easy to see, the values of E~/(~ and (D[~(~162 r ( r e , I1r il -1) are stable relative to small deviations a = II;~ - ~ II of the convolving measure )~. This p r o p e r t y m a y be useful, for instance, w h e n the given convolving measure ~ is difficult to simulate and it has to be a p p r o x i m a t e d by some suitable measure ;~.

6. EXAMPLE

(I/2)dx, o~,o = N i n { 1 , x}, 2 / = ~ 0 , " N = mo = 2. Use Proposition 3 to construct a convolving measure ~9,~ for pair (fig, ff~o) on ball q/~o.~. Let 2~0 = o~o, Let fft~= L2(~, I~), ~ = [ - - l, I1, Ix (dx) =

is identity operator idle ~ on fft~o . For the n o r m of this e m b e d d i n g , we easily obtain the bound nz,oo(,,r 7~', i.e., we m a y take c = 3. T h e n f r o m (2.4) it follows that we m a y take as the convolving measure

) < 1+

Using the convolving measure ~],c-~3, we will now construct the L R U p r o c e d u r e r(I). The vector of functionals h z = (hx, h2)T is chosen in accordance with the measure ~(U f r o m (4.6):

g(I)(dhe) = ~ 1- [det((h~, \(h,, f~)' (h~, f2)'~l~ 7~ (dhZ), where fl(x) = I, f2(x) = ~r"3"x, x E [--1, 1], is an orthonormal basis in Jt% . Let h2Csupp~, ~r

. Then

2

h s (x) = h~i (x)/3, h~ (x) = E f* (x) fi (z) -- 1 + 3xz,

Now f r o m (1.2) and (4.7) we obtain an expression for the estimator: ( ~ ) = S(~Py ~ = 3 [(ylz, - - y,z,) + (y~ --yx)

xl/(z,--zO.

From the convolving measure ~ := )~j,c--~ with the support ~L- = suppk~z.c=3 = {1/3 + zx: z ~ [--1, 1]} w e n o w pass to a convolving measure on the b o u n d a r y n d , , = 0~/l~r of the ball %~o.~ . Clearly, 2/r, w e a k l y majorizes % . As the section 2/,o o f the set 2~m we take the semicircle 2L0 = {a + bx: a 2 + b2/3 = 1, a _>0, b > --4"3-~}in the coordinates a, b/~/~. Let fa = ( 1 / 3 0 r)(z) = r(z/3) Vz ~ [--1, 1], where r(z) = 1 + 3zx. Then Hlla = (1 + 3z2)l/z/3, and 2

1 x --I

244

4

.

,

~,' (dh) = -ff (I -/- 3z*) Xa,~=z ( d ~

Define the mapping ~: (--~-/2, ~r/21 ~ ~

= (1 + 3z'*)

[( 1)]

(Ix) (dz).

x0

such that • (tp) = cos cp -k "I/3-(sin (p) x.

Since fI0]a = ~(~o) ,--* z = (tan ~o)/3, then for an arbitrary Borel subset V o c 2Lo,

where Xvo is the indicator of V o. Let us check the gain that we achieve in the sense of the criterion ~(rx (I)) = tr D[~], say, in this example by 0 passing from the measure ~,~=3 to Lj,c=a as a result of the projection operation. Assuming that the observations are uncorrelated and equiaccurate, we obtain for the interpolation estimator of the element r/(x) -- x 2 (local approach)

A

tr D [~(z)]Intx)=x,,x=~a,c=3 =

= 2 .I
~g

l 1 zx)2--~-dz 9 ~--- 2~
9 1

-}-202-~-~ d z :

18@,

= 2 ~ (P~e~on, ho)2 Z~.c=3(dho) + 9d o

J- 2~2 I )~~ 'c=3 (dh~ : 2 I ~ (dh) + ~ 4zo

(r2 ~a

dq~ -

-

--~x/3cos ~ q~

_

462,

i.e., a gain by a factor of 4.5. LITERATURE CITED 1.

2. 3. 4. 5.

S. M. Ermakov, Monte-Carlo Method and Related Topics [in Russian], Nauka, Moscow (1975). V. P. Kozlov, "Design of regression experiments in functional spaces," in: Mathematical Methods of Experimental Design [in Russian], Nauka, Novosibirsk, (1981), pp. 74-101. M. B. Malyutov, "A comment on experimental design in an infinite domain of action," in: Optimal Experimental Design [in Russian], Mosk. Gos. Univ., Moscow (1975), pp. 164-166. A. B. Uspenskii and V. V. Fedorov, Computational Aspects of the Least Squares Methods in Analysis and Design of Regression Experiments [in Russian], Mosk. Gos. Univ., Moscow (1975). R. K. Mehra, "Optimal input signals for parameter estimation in dynamic systems," IEEE Trans. Autom. Contr., AC-19, No. 6, 753-768 (1974). 245

.

7.

.

E. V. Sedunov and N. G. Sidorenko, "Unbiased experimental design in a Hilbert space," Teor. Veroyatn. Primen., 32, No. 4, 804-808 (1987). E. V. Sedunov and A. V. Lipin, "Choice of distributions of observation functionals in a Monte-Carlo experiment," Proc. 5th International Vilnius Conf. on Probability Theory and Mathematical Statistics [in Russian], Vol. 4, Vilnius (1989), pp. 220-221. S. M. Ermakov and E. V. Sedunov, "On optimal randomized procedures for design and analysis of regression experiments," in: Mathematical Methods of Experimental Design [in Russian], Nauka, Novosibirsk (1981), pp. 141-154.

STRENGTH

AND REINFORCEMENT

OF A NETWORK

AND TREE PACKING

V. A. Trubin

UDC

519.3

We propose strictly polynomial-time algorithms for a number of network problems: (a) strength and reinforcement of a network, (b) attack and density of a network. (c) packing, covering, and partitioning of a network into spanning trees. The proposed algorithms are either new or have lower complexity than previously published algorithms. INTRODUCTION Cunningham [1] considered a number of extremal combinatorial problems connected with the determination of the strength and reinforcement of a network and proposed strictly polynomial-time algorithms for solving these problems. In this paper, we propose algorithms for solving these and other problems which have lower time complexity than Cunningham's algorithms. Let G = G(V, E) be an undirected graph with vertex set V, IVI -- n, and set of edges E, IEI = m. Every edge e ~ E is assigned the weight % _> 0, called its strength. It is interpreted as a measure of effort required to destroy the edge. There are various definitions of the strength of a graph for given edge strengths. In particular, following [1, 2], we define the strength of a graph as

{ c (A).A

cr~---o(c) = min~k(A ) . _ =/= ~

),

(1)

where A _CE is an arbitrary subset of graph edges, c(A) = ~(ce: e 6 A) is the sum of strengths of the edges in A (this sum notation is used throughout the paper), k(A) is the number of additional connected components that appear in G after the edges of A are removed. In other words, k(A) is the number of connected components less one in the graph G(V, E\A). The problem of determining the strength (I) is closely linked with the problem of attack of a network, which involves finding = rain (c (A) - - ak (A) : A ___E)

(2)

for a given nonnegative parameter a. In this case, cr may be interpreted as the reward of the attacker for the destruction of each new component of the network G, and c(A) are the attacker's costs of destructing the set A. The attack problem is thus to find A ___E which maximizes the income.

Translated from Kibernetika, No. 2, pp. 67-75, March-April, 1991. Original article submitted November 28, 1990. 246

0011-4235/91/2702-0246512.50 9

Plenum Publishing Corporation