extfieldsofstudy: Physics Mathematics

text:
Entropy reduction of quantum measurements

It is observed that the entropy reduction (the information gain in the initial terminology) of an efficient (ideal or pure) quantum measurement coincides with the generalized quantum mutual information of a q-c channel mapping an a priori state to the corresponding posteriori probability distribution of the outcomes of the measurement. This observation makes it possible to define the entropy reduction for arbitrary a priori states (not only for states with finite von Neumann entropy) and to study its analytical properties by using general properties of the quantum mutual information. By using this approach one can show that the entropy reduction of an efficient quantum measurement is a nonnegative lower semicontinuous concave function on the set of all a priori states having continuous restrictions to subsets on which the von Neumann entropy is continuous. Monotonicity and subadditivity of the entropy reduction are also easily proved by this method. A simple continuity condition for the entropy reduction and for the mean posteriori entropy considered as functions of a pair (a priori state, measurement) is obtained. A characterization of an irreducible measurement (in the Ozawa sense) which is not efficient is considered in the Appendix.

Introduction
The notion of a quantum measurement plays a key role in quantum theory. One of quantitative characteristics of a quantum measurement is the entropy reduction 1 defined as a difference between the von Neumann entropy of an a priori (pre-measurement) state and the mean von Neumann entropy of the corresponding posteriori (post-measurement) states. Roughly speaking, the entropy reduction characterizes a degree of purifying ("gain in purity") of a state in a measurement process. More details about the information sense of this value can be found in [11,15,21].
An interesting question concerns the sign of the entropy reduction. Groenewold has conjectured in [6] and Lindblad has proved in [12] that the entropy reduction is nonnegative for quantum measurements of the von Neumann-Luders type. The general case has been studied by Ozawa, who has proved in [21] that the entropy reduction is nonnegative if and only if the quantum measurement is quasicomplete (also called irreducible in [19]) in the sense that for an arbitrary pure a priori state the corresponding family of posteriori states consists of pure states (for almost all outcomes). The class of quasicomplete (irreducible) quantum measurements contains the class of efficient or pure measurement (cf. [10,11,15]) described in Section 3.1. Quantum measurements belonging to the gap between these two classes are characterized in the Appendix as measurements with quite singular properties.
In this paper we show that the entropy reduction of an efficient (pure) quantum measurement can be expressed via the (generalized) quantum mutual information of the quantumclassical channel mapping an a priori state to the corresponding posteriori probability distribution of the outcomes of the measurement. This makes it possible to define the entropy reduction for arbitrary a priori states (not only for states with finite von Neumann entropy) and to study its analytical properties by using results concerning the quantum mutual information of infinite-dimensional channels [8].
The paper is organized as follows. In the first part we restrict attention to the case of quantum measurements with a discrete set of outcomes, which is more simple mathematically. In the second part we consider the case of general quantum measurements described by completely positive instruments by generalizing the notion of the quantum mutual information for channels taking values in the space of normal states of an arbitrary W * -algebra.

The discrete case
Let H be a separable Hilbert space, B(H) -the Banach space of all bounded operators in H with the operator norm · , T(H) -the Banach space of all trace-class operators in H with the trace norm · 1 = Tr| · |, containing the cone T + (H) of all positive trace-class operators. The closed convex subset S(H) = {A ∈ T + (H) | TrA = 1} is a complete separable metric space with the metric defined by the trace norm. Operators in S(H) are denoted ρ, σ, ω, ... and called density operators or states since each density operator uniquely defines a normal state on B(H) [3].
The identity operator in a Hilbert space H and the identity transformation of the set T(H) will be denoted I H and Id H correspondingly.
For an arbitrary state ω ∈ S(H ⊗ K) the partial states Tr K ω and Tr H ω will be denoted ω H and ω K .
We will use the following natural extension of the von Neumann entropy H(ρ) = −Trρ log ρ of a quantum state ρ ∈ S(H) to the cone T + (H) of all positive trace-class operators The quantum relative entropy is defined for arbitrary operators A and B in T + (H) as follows where {|i } is the orthonormal basis of eigenvectors of A and it is assumed that H(A B) = +∞ if suppA is not contained in suppB [13]. A linear completely positive trace-preserving map Φ : T(H) → T(H ′ ) is called a quantum channel [9,17].
By the Stinespring dilation theorem there exist a separable Hilbert space H ′′ and an isometry V : The quantum channel is called complementary 3 to the channel Φ, it is uniquely defined up to unitary equivalence [7]. The quantum mutual information is an important entropic characteristic of a channel Φ : T(H) → T(H ′ ) related to the entanglement-assisted classical capacity of this channel [9,17]. In finite dimensions it is defined at arbitrary state ρ ∈ S(H) by the expression (cf. [1]) In infinite dimensions this expression may contain uncertainty "∞ − ∞", but it can be modified to avoid this problem as follows where K is a Hilbert space isomorphic to H,ρ is a purification 4 of the state ρ in the space H⊗K and ̺ = Tr Hρ is a state in S(K) isomorphic to ρ. Analytical properties of the function (ρ, Φ) → I(ρ, Φ) defined by (5) in the infinite dimensional case are studied in [8].
An efficient quantum measurement M with a countable outcome set X = {x i } i∈I is described by a set {V i } i∈I of operators in B(H) such that i∈I V * i V i = I H . Applying this measurement to an arbitrary a priori state ρ ∈ S(H) results in the posteriori probability distribution {π i (ρ)} i∈I , where π i (ρ) = TrV i ρV * i is the probability of the outcome x i , and the corresponding family of posteriori states {ρ i } i∈I , where ρ i = (π i (ρ)) −1 V i ρV * i . Thus i∈I π i (ρ)H(ρ i ) = i∈I H(V i ρV * i ) is the mean entropy of posteriori states. The entropy reduction of the quantum measurement M at an a priori state ρ with finite entropy is the following value Let H X be a Hilbert space having dimension coinciding with the cardinality of the outcome set X. Consider the quantum channel where {|ϕ i } i∈I is a particular orthonormal basis in H X . The channel Π M is a quantum modification of the quantum-classical channel mapping a state ρ to the probability distribution for any state ρ in S(H) with finite entropy. If H ({π i (ρ)} i∈I ) < +∞ this equality directly follows from (4) In general case it can be easily deduced 5 from [8, Proposition 3 and Theorem 1]. Equality (7) obtained under the condition H(ρ) < +∞ makes it possible to consider the entropy reduction of an efficient quantum measurement with a countable outcome set as a function on the whole space of a priori states. Definition 1. The entropy reduction of an efficient quantum measurement M = {V i } i∈I at an arbitrary a priori state ρ is defined as follows where Π M is the quantum channel defined by (6).
By equality (7) this definition is consistent with the conventional one. Its main advantage consists in possibility to study the function ρ → ER(ρ, M) on the whole space of a priori states by using properties of the quantum mutual information (many of them follow from the corresponding properties of the quantum relative entropy). 3) monotonicity: for arbitrary efficient measurements M = {V i } i∈I and N = {U j } j∈J in a Hilbert space H with the outcome sets X and Y the inequality holds for any ρ ∈ S(H), where N • M is the measurement in the space H with the outcome set X × Y determined by the family {U j V i } i∈I,j∈J ; 4) subadditivity: for arbitrary efficient measurements M = {V i } i∈I and N = {U j } j∈J in Hilbert spaces H and K with the outcome sets X and Y the inequality holds for any ω ∈ S(H ⊗ K), where M ⊗ N is the measurement in the space H ⊗ K with the outcome set X × Y determined by the family {V i ⊗ U j } i∈I,j∈J .
" ⇒ " Relations (11) mean that P V * i V i P = π i (ρ)P for each i, where P = k |k k| is the projector on the support of the state ρ. Thus (π i (ρ)) −1/2 V i P is a partial isometry and hence ρ i = (π i (ρ)) −1 V i P ρP V * i ∼ = ρ for each i such that π i (ρ) = 0.
3) This follows from the 1-st chain rule for the quantum mutual information (property 3 in Proposition 1 in [8]). Indeed, Consider the question of continuity of the entropy reduction with respect to "perturbation" of quantum measurements.
Let M(H) be the set of all efficient quantum measurements in the Hilbert space H with finite or countable set of outcomes identified with the set of all sequences with the topology of coordinate-wise strong operator convergence. Proposition 1 in [8] and Corollary 2 in [8] imply the following assertion.
Proposition 1. The function is lower semicontinuous on the set S(H) × M(H). Let A be an arbitrary subset of S(H) on which the von Neumann entropy is continuous. Then function (12) is continuous on the set A × M(H).
By Proposition 1 and Proposition 6.6 in [18] function (12) is continuous on the set K H,h ×M(H), where K H,h is the set of states with the mean energy TrHρ not exceeding h > 0 provided the Hamiltonian H of the quantum system satisfies the condition Tre −λH < +∞ for all λ > 0 (which holds, for example, for the Hamiltonian of the system of quantum oscillators).

On properties of efficient (pure) instruments
A general quantum measurement in a Hilbert space H with the measurable outcome set {X, F } is described by a special mathematical object called instrument, which was introduced by Davis and Lewis [5]. An instrument M (in a space of states) is a σ-additive measure on {X, F } taking values within the set of quantum operations -completely positive tracenon-increasing linear transformations of T(H) such that M(X) is a channel (see the detailed definition in [2,9,14]).
Let ρ be an arbitrary a priori state in S(H). Then the outcome of the measurement M is contained in a set F ∈ F with probability TrM(F ) [ρ]. If this probability is nonzero is the corresponding posteriori state of the system. Thus is the posteriori probability measure on the outcome set {X, F } corresponding to the a priori state ρ.
Ozawa proved in [20] existence of a family {ρ x } x∈X of posteriori states defined for µ ρ -almost all x such that the function x → TrAρ x is F -measurable for any A ∈ B(H) and By using the family {ρ x } x∈X one can consider the mean entropy of posteriori state X H(ρ x )µ ρ (dx) and assuming that H(ρ) < +∞ one can define the entropy reduction as follows This is a natural generalization of the entropy reduction considered in Section 2 for the class of measurements with a countable set of outcomes.
Ozawa proved in [21] that ER(ρ, M) is nonnegative if and only if the instrument M is irreducible in the sense of the following definition. 7 Definition 2. An instrument M is called irreducible if for an arbitrary pure a priori state ρ the posteriori states ρ x are pure for µ ρ -almost all x.
An arbitrary instrument M in a Hilbert space H can be represented as follows 8 where V is an isometry from H into H ⊗ H 0 and P (F ) is a spectral measure in H 0 [19] (see also [10]).
The following notion introduced in [10] is a natural generalization of the notion of an efficient measurement with a countable outcome set.
Definition 3. An instrument M is called efficient or pure if it has representation (13) with the spectral measure P (F ) of multiplicity one. 9 In [10] it is shown that an efficient instrument is irreducible. The converse assertion is not true (see Example 1 in the Appendix). A characterization of a quantum instrument, which is irreducible but not efficient, and a simple sufficient condition providing equivalence of efficiency and irreducibility are presented respectively in Proposition 5 and in Corollary 3 in the Appendix. This characterization shows that a quantum instrument, which is irreducible but not efficient, has quite singular properties.
It is the class of efficient instruments to which the results of Section 2 can be extended. We will use the following characterization of such instruments, where M ⊗ J K denotes the instrument M(·) ⊗ Id K in the Hilbert space H ⊗ K with the outcome set of the instrument M.
Proposition 2. Let M be an instrument in a Hilbert space H with the outcome set {X, F }. The following statements are equivalent: for any ϕ ∈ D, F ∈ F , A ∈ B(H).
(v) statement (iv) holds with D = lin{|ϕ i }, where {|ϕ i } is a given arbitrary orthonormal basis in H.
Proof. (i) ⇒ (iii). It is easy to see that the instruments M and M ⊗ J K have representation (13) with the same spectral measure. Hence efficiency of M is equivalent to efficiency of M ⊗ J K . As mentioned after the proof of Theorem 1 in [10] any efficient instrument is irreducible.
(iii) ⇒ (ii) is obvious, since the instrument in (ii) can be considered as a restriction of the instrument in (iii).
(ii) ⇒ (v). By Theorem 1 in [10] and its proof there exist a positive σ-finite measure µ on {X, F } and a countable family is an orthonormal basis of the space K. By using the polarization identity it is easy to show that Hence for the instrument M ⊗ J K and a pure a priori stateρ = |φ φ| (whereφ ∈ D) we have while the posteriori state corresponding to the outcome x ∈ X \ X ŝ ϕ iŝ is a set such that µρ(X ŝ ϕ ) = 0 [10]. By noting that the instrument M ⊗ J K is irreducible and by using (14) one can show existence of a set Xφ ∈ F such that µ(X \ Xφ) = 0 and the above stateρ x is pure for any x ∈ Xφ \ X ŝ ϕ . Let D 0 be a countable subset of D consisting of finite linear combinations of the vectors of the family {ϕ i ⊗φ j } ij with rational coefficients. Let X 0 = φ∈ D 0 Xφ ∈ F . Then µ(X \X 0 ) = 0 and the stateρ x defined by (15) is pure for allφ ∈ D 0 and all x ∈ X 0 \X ŝ ϕ . Hence the family {| V k (x)φ } k consists of collinear vectors for allφ ∈ D 0 and all x ∈ X 0 . Since the rank of the (v) ⇒ (vi) is obvious.
(iv) ⇒ (i). By the condition the linear operator is isometrical and hence it can be extended to the isometry V from H into H ⊗ L 2 (X, F , µ). A direct verification shows that is the indicator function of the set F ∈ F . Thus the instrument M is efficient.
We will also use the following simple observations.
Proof. It is easy to show that the instruments N•M and M⊗N have representation (13) with the spectral measure P M ⊗ P N , where P M and P N are spectral measures corresponding to the instruments M and N.

A representation of the entropy reduction
To extend the results of the previous section to the case of general type measurement consider the construction proposed by Barchielli and Lupieri in [2]. Choose a positive complete measure µ 0 on (X, F ) such that µ ρ is absolutely continuous with respect to µ 0 for all ρ in S(H) (this can be done by using the measure µ ρ 0 , where ρ 0 is a given full rank state in S(H)). Let L ∞ (X, F , µ 0 , B(H)) be the W*-algebra of µ 0 -essentially bounded B(H)-valued weakly* measurable functions on X with the predual Banach space L 1 (X, F , µ 0 , T(H)) of T(H)-valued Bochner µ 0 -integrable functions on X. By Theorem 2 in [2] with an arbitrary instrument M one can associate a channel Λ * M : The preadjoint channel Λ M : T(H) → L 1 (X, F , µ 0 , T(H)) produces the posteriori family as follows where σ(x) is a particular representative of the class Λ M (ρ), while the function Trσ(x) is a probability density (the Radon-Nikodym derivative) of the measure µ ρ with respect to the measure µ 0 . Consider the channel Π * M : L ∞ (X, F , µ 0 ) → B(H) defined by the relation The preadjoint channel Π M : T(H) → L 1 (X, F , µ 0 ) maps an arbitrary a priori state ρ to the probability density of the posteriori measure µ ρ with respect to the measure µ 0 and hence it can be considered as a natural generalization of the channel Π M defined by (6).
Since the channel Π M defined by (17) has no purely quantum modification, to extend the results of Section 2 we have to generalize the notion of quantum mutual information.
where K is a Hilbert space isomorphic to H,ρ is a purification of the state ρ in the space H ⊗ K, ̺ = Tr Hρ is a state in S(K) isomorphic to ρ and H(· ·) is the relative entropy for two states in (A ⊗ B(K)) * .

Remark 1.
It is natural to ask about validity for the above-defined value of the properties of the quantum mutual information of a purely quantum infinite dimensional channel presented in Propositions 1 and 4 in [8]. Since the proofs of these propositions can not be directly generalized to the case of a channel considered in Definition 4, the above question is not trivial.
Here we note only that for an arbitrary channel Φ : T(H) → A * the function ρ → I(ρ, Φ) is nonnegative and lower semicontinuous and that for an arbitrary channel Ψ : A * → B * , where B is an other W * -algebra, the inequality I(ρ, Ψ • Φ) ≤ I(ρ, Φ) holds for all ρ (the 1-st chain rule). These properties follow from nonnegativity and lower semicontinuity of the relative entropy, Lemma 2 in [8] and Uhlmann's monotonicity theorem [18].
The relative entropy for two states σ 1 and σ 2 in L 1 (X, F , µ 0 , T(H)) can be expressed as follows where µ 1 (dx) = Trσ 1 (x)µ 0 (dx) (see [2, formula (4)]). In this expression H q denotes the quantum relative entropy for two positive trace class operators defined by (1), while H c denotes the classical relative entropy for two probability measures, that is H c (µ 1 µ 2 ) = X log Trσ 1 (x) Trσ 2 (x) µ 1 (dx). For an arbitrary instrument M equality (7) does not hold, but one can prove the following estimation. Let {ρ x } be the family of posteriori states obtained via a given representative of the class Λ M (ρ) by the rule similar to (16). It is easy to see that {ρ x . = Tr Kρx } is the family of posteriori states for the instrument M corresponding to the a priori state ρ. Since the instrument M is localized in the space H we have X Tr Hρx µ ρ (dx) = Tr Hρ = ̺ ∼ = ρ. By using expression (18) we obtain By the triangle inequality the absolute value of the last term in this expression is majorized by X H(ρ x )µ ρ (dx).
where Π M is the quantum-classical channel defined by (17).
The following theorem is an extended version of Theorem 1.
holds for any ρ ∈ S(H); 10 4) subadditivity: for arbitrary efficient instruments M and N in separable Hilbert spaces H and K the inequality holds for any ω ∈ S(H ⊗ K). 11 Proof. By Definition 5 lower semicontinuity of the function ρ → ER(ρ, M) follows from the second part of Remark 1.
Concavity of the function ρ → ER(ρ, M) on the convex subset of states with finite entropy follows from inequality (56) in [2]. Concavity of this function on the set S(H) can be proved by using lower semicontinuity of this function and Lemma 2 below (see the proof of Proposition 1 in [8]).
Below we will use the notations introduced in the proof of Proposition 3. 1) Note that "⇐" Let ̺ x = Tr Hρx . Since the instrument M is irreducible (by Proposition 2), we have ρ x ∼ = ̺ x for µ ρ -almost all x and hence ̺ x ∼ = ̺ = Tr Hρ for µ ρ -almost all x. Since the instrument M is localized in the space H, we have ̺ = X ̺ x µ ρ (dx). Thus Lemma 6 in the Appendix implies (21).
2) This property follows from identity (24) in Lemma 3 below, since the both summands in the left side of this identity are lower semicontinuous functions on the set S(H) by the second part of Remark 1.
3) This follows from the 1-st chain rule for the generalized quantum mutual information mentioned in the second part of Remark 1. Indeed, let µ 0 be a measure on {X × Y, F ⊗ E} chosen in accordance with the Barchielli-Lupieri construction for the instrument N • M and ν 0 be a measure on for any F ∈ F and ρ ∈ S(H). Hence the measure ν 0 can be used in the Barchielli-Lupieri construction for the instrument M. Let Ξ be a channel from L 1 (X × Y, F ⊗ E, µ 0 ) to L 1 (X, F , ν 0 ) preadjoint to the channel .
which can be proved easily by noting that N(Y ) is a trace preserving map. 4) Let µ 0 and ν 0 be measures on {X, F } and on {Y, E} chosen in accordance with the Barchielli-Lupieri construction for the instruments M and N correspondingly. Then for the instrument M ⊗ N one can take the measure µ 0 ⊗ ν 0 . By noting that it is easy to show that Λ * M⊗N = Λ * M ⊗ Λ * N . Let ω be a state in S(H ⊗ K) such that H(ω H ) and H(ω K ) are finite. Then inequality Proof. Let K ∼ = H and P n = n i=1 |e i e i | be a projector in K, n = 1, 2... Consider the value λ i λ j |e i e j | ⊗ |e i e j |,ρ n = c −1 n I H ⊗ P n ·ρ 0 · I H ⊗ P n , ̺ 0 = Tr Hρ0 , ̺ n = Tr Hρn and Ψ n (·) = P n (·)P n is a map from T(K) to itself. We will show that lim Let σ 1 (x) and σ 2 (x) be representatives of the classes Π M ⊗ Id K (ρ 0 ) and Π M (ρ 0 ) ⊗ ̺ 0 correspondingly. Then c −1 n P n σ 1 (x)P n and c −1 n P n σ 2 (x)P n are respectively representatives of the classes c −1 n Π M ⊗ Ψ n (ρ 0 ) and c −1 n Π M (ρ 0 ) ⊗ Ψ n (̺ 0 ). Expression (18) implies Hence (23) follows from Lemma 4 in [13] and the monotone convergence theorem. By using expression (18) we obtain since c n µ ρn (F ) ≤ µ ρ 0 (F ) for all F ∈ F . Hence lim n (I n − ER(ρ n , M)) = 0. This and (23) imply the assertion of the lemma.
Proof. Since the instrument M is irreducible (by Proposition 2) and is localized in the space H we have H(ρ x ) = 0 for µ ρ -almost all x ∈ X and X Tr Hρx µ ρ (dx) = Tr Hρ = ̺ ∼ = ρ. By using expression (18) we obtain This expression and Corollary 1 imply (24).

Remark 2.
By proving concavity of the function ρ → I(ρ, Λ M ) and by using Lemma 6 in [23] one can show validity of equality (24) for any ρ in S(H). By comparing this equality with the assertion of Theorem 1 in [8] we see that the channel Λ M plays the role of the complementary channel to the channel Π M . Strictly speaking, this holds in the discrete case when the q-c channel Π M can be considered as a purely quantum channel (see Section 2).
The first assertion follows from lower semicontinuity of the relative entropy with respect to pointwise convergence of states [18,Corollary 5.12].
. By means of (27) it is easy to show that the last three terms in this expression are less than ε A for all n = 0, 1, 2, ... As proved before (25) implies that the first term tends to X TrP ε A(x)P ε σ 0 (x)µ 0 (dx), since P ε A(x)P ε ∈ B(P ε (H)). Thus we conclude that (26) holds.

A characterization of a quantum instrument which is irreducible but not efficient
In for any ϕ ∈ D, F ∈ F , A ∈ B(H). We may assume that for each x the all nonzero operators from the family V k (x) are not proportional to each other, since if V k ′ (x 0 ) = λV k (x 0 ) for some x 0 and λ ∈ C then we may replace V k (x 0 ) by 1 + |λ| 2 V k (x 0 ) and consider that V k ′ (x 0 ) = 0.
The instrument M is efficient if and only if V k (x) = 0 for k > 1 and µ-almost all x. This follows from the proof of Theorem 1 in [10] and the proof of the implication (iv) ⇒ (i) in Proposition 2.
So, if the instrument M is not efficient then there exists a subset F s of X such that M(F s ) = 0 and V 2 (x) = 0 for all x ∈ F s . 12 Proposition 5. If the instrument M is irreducible but not efficient then for µ-almost all x in F s the all nonzero operators V k (x) has the same one dimensional range (depending on x), that is V k (x)|ϕ = ω k (x)[ϕ]|ψ x for all ϕ ∈ D, where ω k (x) is a linear functional defined on D (not necessary bounded) and ψ x is a unit vector in H (not depending on ϕ). This means that for any ϕ ∈ D, A ∈ B(H) and F ∈ F such that F ⊆ F s . It follows that for an arbitrary a priori state ρ the posteriori state is ρ x = |ψ x ψ x | for µ ρ -almost all x ∈ F s (that is, ρ x does not depend on ρ).
This assertion can be obtained by using the arguments from the proof of the implication (ii) ⇒ (iv) in Proposition 2 with dim K = 1. The only difference appears at the point where Lemma 5 is used, since in this case we can not exclude the possibility of rankV k (x) = 1. It is this possibility that prevents to prove that any irreducible instrument is efficient. Proof. Let M be a instrument in a Hilbert space H with the outcome set {X, F }, which is irreducible but not efficient. By Proposition 5 there exists a positive σ-finite measure µ on {X, F }, a subset F of X such that M(F ) = 0, a dense domain D ⊆ H, a family {x → ω k (x)} k of functions on F , such that ω k (x) is a linear functional defined on D for each x ∈ F , and a function x → ψ x on F such that ψ x is a unit vector in H for each x ∈ F , for which relation (28) holds. By using the polarization identity one can show that where denotes the Bochner integral.
It follows that the operator M(F ) ⊗ Id K (ω) is separable. Since an arbitrary pure state in S(H⊗K) can be approximated by a sequence of above-considered states, the operator M(F )⊗Id K (ω) is separable for any state ω ∈ S(H⊗K). Thus the operation M(F ) is entanglement-breaking. Example 1. Let P be a spectral projector valued measure on a measurable space {X, F } and |ψ 0 be a fixed unit vector in H. Then the instrument M(F )[ρ] = [TrP (F )ρ]|ψ 0 ψ 0 | is obviously irreducible, but it is efficient if and only if the spectral measure P has (uniform) multiplicity one, since it is easy to see that the spectral measure from representation (13) coincides with P . Note that the channel M(X) : ρ → |ψ 0 ψ 0 | is entanglement-breaking.

Two auxiliary lemmas
Lemma 5. Let L 1 = lin({ϕ i } i∈N ) be a linear space and L 0 1 be a countable subset of L 1 consisting of finite linear combinations of the vectors ϕ 1 , ϕ 2 , ... with rational coefficients. Let {A k } be a finite or countable family of nonzero linear operators from L 1 to a linear space L 2 such that the set {A k (ϕ)} ⊂ L 2 consists of collinear vectors for any ϕ ∈ L 0 1 . If at least one operator in the family {A k } has rank > 1 then A k = λ k A 1 for all k, where {λ k } is a set of nonzero scalars.
Thus we have Hence the vectors A k (ϕ 1 ) and A k (ϕ 2 ) are not collinear. By repeating the above arguments with A k instead of A 1 and A 1 instead of A k we obtain It follows from (30) and (31) that A k (ϕ i ) = λ k A 1 (ϕ i ) for all i ∈ N and hence A k = λ k A 1 .
Lemma 6. Let {π α , ρ α } be a countable or continuous ensemble of states in S(H) such that ρ α ∼ =ρ for all α, whereρ is the average state of this ensemble. Then ρ α =ρ for all α.
The assertion of this lemma follows from existence of a finite strictly convex function on the set S(H) depending only on the spectrum of a state. As the simplest example one can consider the function f (ρ) = Trρ 2 .
I am grateful to A.S.Holevo and the participants of his seminar "Quantum probability, statistic, information" for useful discussion. I am also grateful to the organizers of the program "Quantum information theory" in the Institut Mittag-Leffler (Djursholm, Sweden), where the work was completed, and to the participants of this program, especially, to E.Effros, M.Wolf and C.Palazuelos for the help in solving the particular problems.
This work is partially supported by the program "Mathematical control theory" of Russian Academy of Sciences, by the federal target program "Scientific and pedagogical staff of innovative Russia" (program 1.2.1, contract P 938) and by RFBR grant 09-01-00424-a.


extfieldsofstudy:
Mathematics
Computer Science

text:
Source Localization and Sensing: A Nonparametric Iterative Adaptive Approach Based on Weighted Least Squares

Array processing is widely used in sensing applications for estimating the locations and waveforms of the sources in a given field. In the absence of a large number of snapshots, which is the case in numerous practical applications, such as underwater array processing, it becomes challenging to estimate the source parameters accurately. This paper presents a nonparametric and hyperparameter, free-weighted, least squares-based iterative adaptive approach for amplitude and phase estimation (IAA-APES) in array processing. IAA-APES can work well with few snapshots (even one), uncorrelated, partially correlated, and coherent sources, and arbitrary array geometries. IAA-APES is extended to give sparse results via a model-order selection tool, the Bayesian information criterion (BIC). Moreover, it is shown that further improvements in resolution and accuracy can be achieved by applying the parametric relaxation-based cyclic approach (RELAX) to refine the IAA-APES&BIC estimates if desired. IAA-APES can also be applied to active sensing applications, including single-input single-output (SISO) radar/sonar range-Doppler imaging and multi-input single-output (MISO) channel estimation for communications. Simulation results are presented to evaluate the performance of IAA-APES for all of these applications, and IAA-APES is shown to outperform a number of existing approaches.

I. INTRODUCTION
The goal of array processing is to estimate the locations and waveforms of sources by combining the received data from multiple sensors so that the desired signal is enhanced, while the unwanted signals, such as interference and noise, are suppressed. In active sensing applications such as radar/sonar range-Doppler imaging, the aim is to find targets present in a region of interest. For channel estimation in communications, the aim is to estimate the non-zero channel taps and their Doppler shifts, which are then fed to the subsequent equalizer for symbol detection. Low numbers of snapshots and low signal-to-noise ratios (SNR) are among the many challenges that array processing systems frequently face. Another challenge is the presence of nearby sources, in terms of location or Doppler, since closely spaced sources are harder to discriminate. Herein both passive array processing and active sensing are considered.
The most basic approach to array processing is the classical delay-and-sum (DAS) method, in which the received signal from each sensor is weighted and delayed so as to focus on different points in space. However, this method suffers from low resolution and high sidelobe levels. There is a vast amount of literature on methods that provide superior performance over the DAS approach when certain assumptions are met [1]. The well-known standard Capon beamformer (SCB) [2] and multiple signal classification (MUSIC) [3,4] methods provide superresolution when the sources are uncorrelated and the number of snapshots is high. Many extensions to these methods have been proposed to deal with modelling errors, such as steering vector mismatches. (See, e.g., [5]- [9].) However, none of these methods is able to cope with very low snapshot numbers, coherent or highly correlated sources, or severe noise.
Only a few snapshots are available when the environment being sensed by the array is stationary for a short duration of time. Moreover, to avoid smearing, i.e., losing resolution because of wide main beamwidths in the array response, averaging can only be done over a small bandwidth [10,11]. Therefore the number of available snapshots, which is directly related to the time-bandwidth product, can be very small, sometimes as small as 3, for applications such as underwater array processing. Furthermore, as discussed later, the data models for single-input single-output (SISO) radar/sonar range-Doppler imaging and multi-input single-output (MISO) channel estimation in communication problems are similar to the model used in array processing with a single snapshot and an arbitrary array geometry (dictated by the probing waveforms).
The array processing problem has been carried into the sparse signal representation area by noticing that the number of actual sources is usually much smaller TABLE I Notation used in the Text k ¢ k 0`0 -norm k ¢ k 1`1 -norm k ¢ k 2`2 -norm k ¢ k F Frobenius norm of a matrix the Hadamard (elementwise) matrix product tr (¢) trace of a matrix (¢) T transpose of a vector or matrix (¢) H conjugate transpose of a vector or matrix than the number of potential source points that can be considered [12][13][14][15][16][17][18][19][20][21][22][23][24][25][26][27][28][29]. Sparsity-based techniques have also been used in spectral estimation [30], image processing, and array design [31][32][33], among many other application areas. Sparse signal representation algorithms can deal with a few snapshots (even one). However, they may require large computation times and the fine tuning of one or more hyperparameters. Application areas, ranging from passive source localization to active radar/sonar range-Doppler imaging and channel estimation for communications are addressed here. Section II considers passive sensing applications and describes a weighted least squares-based iterative adaptive approach for amplitude and phase estimation (IAA-APES). The algorithm is named IAA-APES herein since its derivation resembles that of the amplitude and phase estimation (APES) algorithm [34][35][36]. (See Section IIC.) This name also distinguishes it from the maximum likelihood (ML)-based iterative adaptive approach (IAA-ML) discussed in the Appendix to further motivate IAA-APES. Using the Bayesian information criterion (BIC) [37,38], IAA-APES can be extended to yield point source estimates. (This approach is referred to as IAA-APES&BIC.) Next, a parametric relaxation-based cyclic approach, namely RELAX [39,40], is discussed as a way to further refine the results of IAA-APES&BIC. (This approach is referred to as IAA-APES&RELAX.) Section III presents the data models for the aforementioned active sensing applications and emphasizes the similarities to the passive sensing case. IAA-APES is evaluated via comprehensive simulations in Section IV, and the IAA-APES' performance is compared with that of a number of existing approaches.
Notation: We denote vectors and matrices by boldface lowercase and boldface uppercase letters, respectively. The kth component of a vector x is written as x k . The kth diagonal element of a matrix P is written as P k . See Table I for other symbols and their meanings.

II. PASSIVE SENSING
In passive sensing applications such as aeroacoustic noise measurements [41] and underwater acoustic measurements [42], an array of sensors is used to estimate the desired source characteristics. This section first introduces the data model for such applications and then the IAA-APES algorithm in this model.

A. Data Model
Consider the wavefield generated by K sources located at μ, where μ ¢ =[μ 1 , μ 2 , :::, μ K ] and μ k 1 are the location parameters of the kth signal, k = 1,:::, K. In the narrowband, multi-snapshot case, the M £ 1 array output vector of an M element array in the presence of additive noise can be represented as [5,43] y(n) = A(μ)s(n) + e(n), n = 1,:::, N where N is the number of snapshots, A(μ) is the a(μ 2 ), :::, a(μ K )], and s(n) ¢ =[s 1 (n), s 2 (n), :::, s K (n)] T , n = 1,:::, N, is the source waveform vector at time n. The array steering matrix has different expressions, depending on the array geometry and on whether the source is in the near-field or far-field of the array. For instance, the steering vector corresponding to the kth source for a far-field linear array (where μ k represents the impinging angle of source k in this case) is given by a(μ k ) = [e ¡j(2¼f=c 0 )x 1 cos(μ k ) , :::, e ¡j(2¼f=c 0 )x M cos(μ k ) ] T (2) where f is the center frequency, c 0 is the wave propagation velocity, and x m is the position of the mth sensor, m = 1,:::, M. (See Fig. 1.) Note that for a planar array or near-field sources, only the expressions for the steering vectors have to be modified; the algorithms that are presented can be applied without any modifications, since a(μ) is assumed to be a known function of μ. The number of sources, K, is usually unknown; hence, here, K is considered to be the number of scanning points in the region. In other words every point of a predefined grid that covers the region of interest is considered as a potential source whose power is estimated. Consequently, K will be much larger than the actual number of sources present, and only a few components of fs(n)g will be non-zero. This is the main reason why sparse algorithms can be used in array processing applications.

B. Related Work
We focus our attention on array processing algorithms exploiting sparsity, which have gained noticeable interest recently. Sparse signal representation aims at finding the sparsest s, such that y = As is satisfied, i.e., to minimize ksk 0 , such that y = As, where A is known and y is measured. The problem in its original form is a combinatorial problem and is nondeterministic polynomial-time (NP) hard, making it impractical [12]. Fortunately, when s is sufficiently sparse [12][13][14][15], ksk 0 can be replaced by ksk 1 , which leads to a convex optimization problem that can be solved much more easily by using, for instance, the least absolute shrinkage and selection operator (LASSO) [16] or basis pursuit (BP) [17] algorithms. Alternatively, the focal underdetermined system solution (FOCUSS) algorithm [18], which is derived using Lagrange multipliers, can be used to iteratively solve the sparse problem. A Bayesian approach, such as sparse Bayesian learning (SBL) [19,20] or the approach in [21], can also be used to estimate s. The algorithms mentioned up to this point are for the single-snapshot case only. The extensions of FOCUSS and SBL to the multiple-snapshot case are M-FOCUSS [22] and M-SBL [23], respectively. Another algorithm, the`1-SVD (singular value decomposition) algorithm [24,25] is similar to BP or LASSO, but this algorithm can work with multiple snapshots. (For the single-snapshot case,`1-SVD becomes a LASSO and BP type of method.) M-FOCUSS requires the tuning of two hyperparameters, which might affect the performance of the algorithm significantly.`1-SVD requires the tuning of a hyperparameter and an estimate for the number of sources. Moreover, implementing`1-SVD requires convex optimization software, such as SeDuMi [44]. M-SBL does not require any hyperparameters. However, M-SBL converges quite slowly in its original form [19,20,23].
Besides the above algorithms, which are the focus of our attention in the numerical examples, there are other sparsity based approaches worth mentioning. Reference [26] adds an additional spatial sparsity regularizing term (an`2-norm constraint) to the`1-norm constraint, and it minimizes a cost function similar to that of`1-SVD. However, this method has two hyperparameters, assumes that the source waveforms can be represented by a sparse basis, and has high computational complexity [26]. Fuchs [27,28] uses a sparsity-constrained deconvolution approach that assumes the sources are uncorrelated and that the number of snapshots is large. The sparsity-constrained solution is obtained with a LASSO or BP type of algorithm. Reference [29] introduces two hyperparameter free deconvolution algorithms exploiting sparsity: a sparsity-based extension to the deconvolution approach for the mapping of acoustic sources (DAMAS) [45] (which is similar to [27] and [28] and widely used in practice) and a sparsity based covariance-matrix fitting approach. Extensions to the correlated source case are also provided. However, the methods in [29] are based on the sample covariance matrix, and hence, these methods do not work well with a limited number of snapshots.

C. IAA-APES
IAA-APES is a data-dependent, nonparametric algorithm based on a weighted least squares (WLS) approach. Let P be a K £ K diagonal matrix, whose diagonal contains the power at each angle on the scanning grid. Then P can be expressed as js k (n)j 2 , k = 1,:::, K: Furthermore, define the interference (signals at angles other than the angle of current interest μ k ) and noise covariance matrix Q(μ k ) to be where R ¢ = A(μ)PA H (μ). Then the WLS cost function is given by (see, e.g., [34]- [36] and [43]) where kxk 2 x and s k (n) represents the signal waveform at angle μ k and at time n. Minimizing (5) with respect to s k (n), n = 1,:::, N, yieldŝ , n = 1,:::, N: (6) This looks like the result that would be obtained by employing APES [34][35][36], but it is actually different than APES since APES obtains Q(μ k ) from the data by forming subapertures, while IAA-APES computes Q(μ k ), as in (4). Moreover, IAA-APES is iterative, but APES is not, and APES cannot be used with arbitrary array geometries. Using (4) and the matrix inversion lemma, (6) can be written aŝ , n = 1,:::, N: This avoids the computation of Q ¡1 (μ k ) for each scanning point, i.e., K times. Moreover, fŝ k (n)g can be computed in parallel for each scanning point, which makes IAA-APES amenable to implementation on parallel hardware. IAA-APES is summarized in Table II. Since IAA-APES requires R, which itself depends on the unknown signal powers, it has to be implemented as an iteration. The initialization is done by a standard DAS beamformer. Our empirical experience is that IAA-APES does not provide significant improvements in performance after about 15 iterations. In IAA-APES, P and, hence R, are obtained from the signal estimates of the previous iteration and not from the snapshots as in conventional adaptive beamforming algorithms, such as SCB, which fails to work properly with coherent or highly correlated sources, or few snapshots [43]. The Appendix provides an alternative derivation of IAA-APES, based on the ML principle. IAA-APES is shown to be an approximation of the IAA-ML algorithm, which is locally convergent due to cyclically maximizing the likelihood function. Hence, the analysis in the Appendix provides an approximate calculation that shows the local convergence of IAA-APES.
Because P is assumed to be a diagonal matrix, one degree of freedom (DOF) is needed to suppress one interfering source. This may lead to a larger than necessary reduction of the number of degrees of freedom when some of the interfering sources are coherent since the cancellation of multiple coherent interfering sources would require only one DOF if the correct structure of P were known. However, we do not assume that the true structure of P is known. Moreover, it is the diagonal structure of P assumed by IAA-APES that makes the algorithm work properly even for low number of snapshot cases and coherent sources.

D. IAA-APES&BIC
In many applications it is desirable to obtain point estimates rather than a continuous spatial estimate. To achieve this sparsity we incorporate a model-order selection tool, i.e., the BIC [37,38], into IAA-APES. Let P denote a set containing the indices of the peaks selected from the IAA-APES spatial power spectrum estimate. Also let I denote the set of the indices of the peaks selected by the BIC algorithm so far. The IAA-APES&BIC algorithm works as follows: first the peak, from the set P, giving the minimum BIC is selected. Then the second peak, from the set P ¡ I, which together with the first peak gives the minimum BIC, is selected, and so on, until the BIC value does not decrease anymore. 2 The IAA-APES&BIC algorithm is summarized in Table III. BIC i (´) is calculated as follows (see [38]) where´= jIj + 1, jIj denotes the size of the set I, i is the index of the current peak under consideration, and fŝ j (n)g N n=1 is the IAA-APES signal waveform estimate corresponding to angle μ j , j 2 fI [ ig. Note that the second term on the right side of (8) does not matter to peak selection; it matters only when (8) is used to select the number of peaks to retain.

E. IAA-APES&RELAX
RELAX [39,40] is a parametric cyclic algorithm that requires an estimate of the number of sources in the field. The results of IAA-APES&BIC can be used to provide a good initial estimate for the last step of RELAX. This approach is outlined in Table IV. The RELAX iterations can be terminated when the norm of the difference between two consecutive estimates is smaller than a certain threshold (5 £ 10 ¡4 for the examples considered herein). The maximization , n = 1,:::, N end for until (convergence) step of the algorithm can be implemented without much computational effort by means of a fine search only around the peak values of the IAA-APES&BIC result. 3 RELAX can be useful in estimating off-grid sources accurately and for further improving the IAA-APES waveform and angle estimates.

III. ACTIVE SENSING
In active sensing applications, besides the receiver, there are also one or more transmitters. The radar/sonar range-Doppler imaging problem for a SISO system is first investigated in this section. Then the channel estimation problem for MISO communications is discussed.

A. Range-Doppler Imaging
Pulse compression refers to the process of transmitting a modulated pulse and then matched filtering the returned signal, which arrives at the antenna altered by complex coefficients that bear target information [48].
where M is the pulse length. Let  3 The fine search can be implemented efficiently using the fast Fourier transform (FFT) [39,40] or a derivative-free uphill search method, such as the Nelder-Mead algorithm [46,47]. Note that the latter method is available in the MATLAB optimization toolbox with the name of "fminsearch." the Doppler interval of interest is divided into L bins, and the Doppler frequency for the lth Doppler bin is denoted as ! l . Then the M samples of the received signal that is temporally aligned with the return from the range bin of current interest r (see Fig. 2) can be represented by for r = 1,:::, R, where ® r,l (which is proportional to the complex "voltage" radar-cross section (RCS) of the corresponding target) denotes the complex amplitude of the returned signal from the range bin of current interest r and the lth Doppler bin f® m+r,l g denote the complex amplitudes of the returned signals from the adjacent range bins, and e r denotes the noise.
The reflections from nearby range bins are considered to be clutter. The M £ M shift matrix J m takes into account the fact that the clutter returns from adjacent range bins need different propagation times to reach the radar/sonar receiver: for m = 0,:::, M ¡ 1. Equation (12) can be written as Note that (12) is similar to the data model for passive sensing arrays, see (1), but with a single snapshot. The IAA-APES estimate at iteration number i 2 f1, 2, :::g becomes® for l = 1,:::, L, r = 1,:::, R, where Here IAA-APES is applied in a slightly different manner than in the passive array processing case. When ® r is to be estimated, the previous values of f® r+m g m=M¡1 m=¡M+1 are used to estimate R(r). However, only ® r is updated using R(r) and y r . When all f® r g R r=1 are updated in this way, we advance to the next IAA-APES iteration. IAA-APES is initialized by matched filtering, matched to each range and Doppler bin, to obtain the initial f® r,l g.
2) Related Work: Matched filtering has been widely used for pulse compression because it gives optimal signal-power-to-output-power performance in the presence of a single target and white noise. However, in practical radar/sonar systems, matched filter performance is far from desirable since the pulse compression problem is usually clutter limited rather than noise limited (see, e.g., [49] and [50]). Many data independent (see, e.g., [49]- [54]) and data-adaptive (see, e.g., [48] and [55]) approaches have been proposed to achieve improved pulse compression.
Data independent approaches can be designed off-line, and hence, these approaches are convenient for real-time implementations in practical systems. Although receive filters based on data-independent instrumental variables (IV) can be used to achieve excellent pulse compression for the negligible Doppler case, their performance is unsatisfactory in the nonnegligible Doppler case because of high sidelobe level problems [49]. On the other hand data-adaptive approaches result in better performance but at the cost of implementation complexity. Two important data-adaptive methods for pulse compression are the adaptive pulse compression (APC) [48] and the Doppler-compensated APC (DC-APC) [55] algorithms. APC is an iterative minimum mean-squared error (MMSE) based data adaptive approach, and DC-APC is the extension of APC to the nonnegligible Doppler case. However, an IV approach [49] may be preferred to APC since the sidelobe level of the former method can be made arbitrarily low and because the filter coefficients can be computed off-line, whereas APC updates the filter coefficients iteratively and adaptively. In the nonnegligible Doppler case, however, adaptive approaches can perform much better. DC-APC is purported to work with at most one target per range bin, and the method used in [55] to estimate the Doppler values is not appealing from a performance viewpoint. On the other hand, IAA-APES can work with multiple Doppler targets located at the same range bin, and IAA-APES estimates the Doppler values in a robust manner. Moreover, APC and DC-APC require the tuning of hyperparameters, whereas IAA-APES is hyperparameter free. Some other differences are discussed below.
DC-APC assumes that there is at most one target per range bin. Let f® r¡M+1 , :::, ® r+M¡1 g and f! r¡M+1 , :::,! r+M¡1 g denote the complex amplitudes and the Doppler frequencies, respectively, of the targets in the corresponding range bin r. DC-APC estimates the target parameters iteratively as follows for r = 1,:::, R, where Q r is the true noise covariance matrix of e r , which is assumed to be known, and i 2 f1, 2, :::g represents the current iteration number. The initial estimates of f® r+m g M¡1 m=¡M+1 are obtained by using a standard matched filter that neglects the Doppler effect [55]. DC-APC also requires the estimates f! r+m g M¡1 m=¡M+1 of the target Doppler frequencies at each iteration. The Doppler frequency estimation approaches suggested in [55] are ad-hoc and not very accurate, especially for large Doppler shifts. This limitation of DC-APC, though, can be easily corrected by replacing! r in (20) with all possible Doppler frequencies f! l g to deal with multiple targets per range bin and to form range-Doppler images.
The DC-APC iterations defined in (20)-(21) result in the numerical ill-conditioning of R (i¡1) (r). To mitigate this problem, [48] suggests using j® (i¡1) r j ± in (20) instead of j® (i¡1) r j 2 , and ¾ ± instead of ¾ 2 , where 0 · ± · 2 and where the noise e r is assumed to be white with a known variance ¾ 2 . This approach requires the delicate tuning of ± (at each iteration), but [48] and [55] do not provide a clear guideline on how to do this. We remark that if the noise covariance matrix Q r in (21) is set to zero, then APC/DC-APC becomes identical to FOCUSS, with the sparsity parameter p = 0 and the regularization parameteŗ = 0. (See, e.g., (16) in [22]). In addition, with the introduction of ±, APC/DC-APC is still identical to FOCUSS, now with 1 ¡ p=2 = ±=2 and¸= ¾ ± . We also note that both APC/DC-APC and FOCUSS are related to the approaches in [21], [30], and [56]. It is interesting to note that many different ideas lead to the same result.
IAA-APES assumes that multiple targets can exist within the same range bin and that f® r,l g is calculated as in (18), where the term in the denominator can be viewed as the current estimate of j® (i¡1) r j 2 used in (20). This would be best estimate for j® (i¡1) r j 2 , obtained by applying the minimum variance distortionless criterion, had the true covariance matrix been known [5]. One more advantage of IAA-APES is that the parameter estimates are inherently unbiased for the signal of interest, whereas this is not the case in DC-APC (or FOCUSS). Furthermore, in IAA-APES, the statistical properties of e r are assumed unknown and are taken into account implicitly as false targets in the current and adjacent range and Doppler bins; see (19). No matrix inversion problems were encountered with IAA-APES during our numerical simulations because of the unbiasedness property of IAA-APES.

B. Channel Estimation
The purpose of channel estimation in communications is to provide the subsequent equalizer with an accurate channel estimate so that the transmitted signals can be recovered successfully at the receiver side [57,58]. SISO channel estimation for communications problem is similar to SISO radar/sonar range-Doppler imaging, with the only difference being that the delay for the former is due to single-trip propagation, while the delay for the latter results from round-trip propagation. denote the ith transmitted pulse, and let L denote the total number of Doppler bins. Then similar to (12), the received signal that is temporally aligned with the return from the rth tap, r = 1,:::, R, with R denoting the total number of taps of the channel, can be written as where J m was defined in (13), and d(! l ) was defined in (11). When determining the parameters of the ith channel f® r,l (i)g, the term P L l=1 ® r,l (i)s i (! l ) is the signal term, and all other terms in (23) are considered as clutter and noise.
Consequently, IAA-APES can be applied directly to (23) to estimate f® r,l (i)g. Like in radar/sonar range compression problems, to determine f® r,l (i)g with high accuracy, the transmitted pulses need to have both good auto and cross-correlation properties [59,60].
2) Related Work: Most of the demodulation algorithms used in practice rely heavily on the accurate estimation of the channel impulse response. As in many other applications, sparse signal estimation approaches have also been proposed in this context. The main motivation for this is that underwater communications [61][62][63] and wireless channels are appropriately modelled as sparse channels consisting of only a few non-zero taps [64]. The existing approaches we evaluate for sparse channel estimation, besides IAA-APES, include the matching pursuit (MP), orthogonal matching pursuit (OMP) [65][66][67], and least squares matching pursuit (LSMP) [68] algorithms, which have been used for sparse channel estimation and equalization in many applications [69][70][71][72]. It is difficult to determine the stopping criterion when using matching pursuit algorithms, and user intervention is needed.

IV. NUMERICAL EXAMPLES
We evaluate the performance of IAA-APES and compare it with various alternative methods in this section. We first focus on passive sensing applications and then shift our attention to active sensing applications.

A. Passive Sensing Examples
This subsection investigates the performance of IAA-APES, M-FOCUSS, M-SBL and`1-SVD for various passive sensing scenarios. Unless noted otherwise, M-FOCUSS is implemented by setting the sparsity parameter p = 0:8 and fine tuning the regularization parameter¸to get the best results. 4 1 -SVD is implemented by assuming that the number of sources is known a priori and by fine tuning the hyperparameter. Since the fine tuning of the hyperparameters assume knowledge of the true source parameters, the so obtained results of M-FOCUSS and 1 -SVD are impractical. M-SBL is implemented by using the alternative update method for the parameters as described in [19], [20], and [23]. For all approaches considered, the scanning grid is uniform in the range from 1 ± to 180 ± , with 1 ± increment between adjacent grid points, unless noted otherwise.
We consider a uniform linear array with M = 12 sensors and half-wavelength interelement spacing.
The far-field narrowband signal waveforms and the additive noise signals are assumed to be circularly symmetric, independent identically distributed (i.i.d.) complex Gaussian random processes with zero mean and variance ¾ 2 , which is varied to obtain various SNR values. Furthermore, each signal waveform is normalized such that (1=N) P N n=1 js k (n)j 2 = P k , k = 1,:::, K 0 , for a given P k value, where K 0 denotes the true number of sources. SNR is defined as 10 log 10 (P k =¾ 2 ), k = 1,:::, K 0 , in decibels (dB), where ¾ 2 is the noise variance. According to the comments made in the Introduction, we consider very low snapshot cases, viz. N = 3 and N = 1.
First we consider three uncorrelated sources at 60 ± , 82 ± , and 90 ± , with 5 dB, 10 dB, and 10 dB powers, respectively, and with N = 3. The noise power is 0 dB, which results in a minimum SNR of 5 dB. Fig. 3 shows the power and location estimates of the algorithms. The circles and the vertical dotted lines that align with these circles represent the true source locations and powers, and the results of 10 Monte-Carlo trials are shown in each plot. DAS clearly suffers from smearing and leakage. IAA-APES provides a much better result than DAS, with low sidelobes and peaks at the true source locations. Moreover, IAA-APES&RELAX indicates the number of sources and their locations and powers accurately. As observed in Fig. 3(d)-(f), the sparse algorithms encounter source splitting, location bias, and power underestimation problems. Also it is hard to tell how many sources are present by solely using the spatial estimates of the sparse algorithms.
Next Fig. 4 considers three coherent sources at 60 ± , 80 ± , and 90 ± , with 10 dB power each and with N = 3. The source waveforms are assumed to be identical for all three coherent sources. The noise power is 0 dB, resulting in a 10 dB SNR. Similar to Fig. 3, the circles and the vertical dotted lines represent the true source locations and the powers, and the results of 10 Monte-Carlo trials are shown in each plot. We observe that IAA-APES is able to resolve the sources successfully and that IAA-APES&RELAX provides accurate point estimates. On the other hand DAS fails to resolve the two closely spaced sources. The performances of the sparse algorithms are similar to those of the previous example.
Finally Fig. 5(a) compares the total mean-squared error (MSE) (sum of each individual MSE) of the angle estimates of each algorithm with the Cramer-Rao bound (CRB) [5], and Fig. 5(b) compares the total angle estimation bias (sum of each individual bias' modulus) of each algorithm for varying SNR. Two uncorrelated sources are placed at 77:51 ± and 90:51 ± , and N is set to 1. (The angle values are picked so that they are not on the size 1 ± grid used by IAA-APES.) To calculate the MSE and bias, we consider only the signals with the two largest powers as the estimated signals for FOCUSS and`1-SVD. We run the sparse algorithms, with a fine grid of size 0:01 ± , around the true source locations. The sparse algorithms are run with K = 950 scanning points, whereas IAA-APES is run with the same resolution as before, i.e., K = 180. IAA-APES&RELAX is used to estimate the off-grid sources. M-SBL results are not shown because of the excessive computation time needed. Each point in Fig. 5 is the average of 100 Monte-Carlo trials. We observe that IAA-APES&RELAX has both better variance and bias characteristics than the other methods for lower SNR.
Note that FOCUSS and`1-SVD both have two hyperparameters, and their selection affects the performances of these two algorithms significantly. Moreover, a different parameter setting should be used depending on the SNR, N, and the source structure, i.e., the number of sources, source spacing, source power levels, and correlation levels. We were able to tune the parameters relatively easily in our simulation scenarios, but when the problem dimensions are large and when there is no prior knowledge of the scenario, it becomes difficult to find good hyperparameters. M-SBL, on the other hand, does not require any hyperparameters, but it takes the longest time to converge. These are the main reasons why BP or LASSO, which are the single-snapshot counterpart of 1 -SVD, and SBL and FOCUSS, which are the single snapshot counterparts of M-FOCUSS and M-SBL, are not considered in the active sensing examples below.
Assuming K À M, the complexity of each IAA-APES iteration is O(M 2 K). The complexity of the BIC extension is negligible compared to that of IAA-APES, and the complexity of the RELAX extension depends on how many sources IAA-APES&BIC determines, the termination condition, and the method chosen for the maximization step. In our experiments RELAX usually converged faster than the time needed for IAA-APES to converge. The complexities of M-FOCUSS and M-SBL are also O(M 2 K) per iteration [23]. The complexity of`1-SVD, on the other hand, is O(K 3 K 3 svd ) [25], where K svd is the estimate of the number of sources. In our simulations IAA-APES was always faster than M-FOCUSS, M-SBL, and`1-SVD, especially when the SNR was low. Note that the actual number of iterations required for convergence depends heavily on the specific scenario. For example for the scenario considered in Fig. 5 at SNR = 2 dB, the times required by FOCUSS and`1-SVD are 3.9 and 5.6 s, respectively, whereas IAA-APES&RELAX requires 0.1 s on average. 5

B. Active Sensing Examples
This section considers examples for the SISO radar/sonar and the MISO channel estimation problems.
We consider three moving targets with 5 dB power and with Doppler shifts of ¡30 ± , ¡25 ± , and 15 ± and six moving targets with 25 dB power and Doppler shifts of ¡70 ± , ¡55 ± , ¡10 ± , 10 ± , 20 ± , and 60 ± , as shown in Fig. 6(a). The background noise is assumed to be a circularly symmetric i.i.d. complex Gaussian random process, with mean zero and a variance of 0 dB. The number of range bins is set to 100, and the number of Doppler bins is set to 37. The resulting minimum SNR is 5 dB. Fig. 6 shows that the matched filter smears the targets in both the Doppler and range domains significantly. Figs. 6(c)-(e) show that MP, OMP, and LSMP results are not satisfactory in this example. The MP, OMP, and LSMP algorithms are all terminated manually to give the best performance. 6 Fig. 6(f) shows that IAA-APES provides a much more useful result (the target locations and Doppler frequencies being easily observable) than the matched filter. IAA-APES&BIC can estimate the strong targets accurately and the weak targets reasonably well, as shown in Fig. 6(g). IAA-APES&RELAX helps improve the results of IAA-APES&BIC even further, as shown in Fig. 6(h).  IAA-APES spatial estimate, but BIC does not modify either the range-Doppler values or the power levels estimated by IAA-APES, whereas RELAX improves upon the IAA-APES estimates.
2) Channel Estimation: The performance of MP, OMP, LSMP, and IAA-APES are also investigated for the channel estimation problem encountered in communications. We consider six transmitters, viz. I = 6, and a single receiver. The probing pulses used in the simulations are obtained by using a cyclic algorithm to ensure both good auto and cross-correlation properties; see [59] and [60] for details. The sampling frequency is assumed to be 24 kHz. M is chosen to be 1024 (which yields a 42.7 ms pulse duration). The number of delay taps are set at 80 to yield a 3.3 ms of delay span, and 13 Doppler bins are used to cover the range from ¡30 Hz to 30 Hz with 5 ± resolution. The six channels are assumed to be independent of each other, and they are simulated as circularly symmetric i.i.d. complex Gaussian random variables, with mean zero and a variance decreasing exponentially with increasing delay, specifically ¾ 2 k = e ¡0:03(k¡1) , where ¾ 2 k is the variance of the channel tap with delay index k, k = 1,:::, 80. The noise is simulated as a circularly symmetric i.i.d. complex Gaussian random process, with mean zero and a ¡20 dB variance. The locations of the non-zero taps of the channels are also simulated randomly and by trying to mimic practical channel functions encountered in underwater communications, see, e.g., [69] and [70]. The power levels of the channel taps were in the range from ¡30 dB to 0 dB, which results in a minimum SNR of ¡10 dB. Fig. 7 illustrates the performances of the algorithms for the first channel; IAA-APES&BIC provides the best result. The results for the other channels, which are not shown for conciseness, are similar to that for the first channel.

V. CONCLUSIONS
This paper has presented IAA-APES in array processing applications. IAA-APES is a nonparametric, hyperparameter free algorithm that is designed to work under severe snapshot limitations and for uncorrelated, partially correlated, and coherent sources, as well as for arrays with arbitrary geometries. Because of the similarities between many active sensing applications and passive array processing, IAA-APES can be applied to these cases as well, without any essential modifications. The BIC can be used in conjunction with the IAA-APES algorithm to yield sparse solutions, which are desirable in many applications. Furthermore, the application of the parametric RELAX algorithm to the IAA-APES&BIC results provides further performance improvement. Simulations showed that IAA-APES and its variations outperform the most prominent methods in the literature in the corresponding application areas. IAA-APES is believed to be a viable candidate for practical applications since it does not require any hyperparameters, has a simple formulation, provides superresolution, facilitates parallel processing, and shows good performance.

APPENDIX. AN APPROXIMATE ML INTERPRETATION OF IAA-APES
We derive a locally convergent ML-based iterative adaptive approach called IAA-ML. IAA-ML is similar to IAA-APES in nature, and we show that IAA-APES can be obtained as a simplified version of IAA-ML.
The negative log-likelihood function of fy(n)g N n=1 can be represented as where ¡ = (1=N) P N n=1 y(n)y H (n) is the so-called sample covariance matrix. It is assumed that the received signal is a multivariate, complex Gaussian random vector with zero-mean and covariance matrix R and that the snapshots are i.i.d. [5]. Minimizing (25) is equivalent to minimizing the Stein's loss, ¡ ln jR ¡1 ¡ j + tr(R ¡1 ¡ ) [75,76], which stresses the covariance fitting character of the cost function, but without the i.i.d. Gaussian assumptions needed by the maximum likelihood loss function.
Assume that Q(μ k ) is known and that the signal power at μ k is to be estimated. Using the fact that jI + ABj = jI + BAj and the matrix inversion lemma together with (4), it can be shown that minimizing (25), with respect to P k , is equivalent to minimizing where Q(μ k ) and a(μ k ) have been replaced by Q k and a k , respectively, for notational simplicity. Setting the first derivative of (26), with respect to P k , to zero, i.e., f 0 (P k ) = 0, gives The second derivative of (26), with respect to P k , is a H k Q ¡1 k a k (1 + P k a H k Q ¡1 k a k ) 2 and hence f 00 (P k ) is f 00 (P k ) = (a H k Q ¡1 k a k ) 2 (1 +P k a H k Q ¡1 k a k ) 2 (28) which is strictly positive. This means thatP k is the unique minimizer of f(P k ). In principle,P k may be negative. However, since P k represents power, it should be nonnegative. The minimizer of f(P k ) subject to the constraint P k¸0 isP k = max(0,P k ) (29) sinceP k is the unique minimizer of f(P k ) (wheñ P k < 0, f(0) · f(P k ) for 8P k¸0 ). By using the matrix inversion lemma in (27) to replace Q k by R, we get ComputingP k requires knowledge of P k and R (recall that R = A(μ)PA H (μ), where P is a diagonal matrix with fP k g on its diagonal). Therefore the algorithm must be implemented iteratively; the initialization is done with DAS. IAA-ML will be locally convergent if R is recalculated after each P k is updated because of the cyclical maximization of the likelihood function. Note that (30) can be written as (assumingP k¸0 ) By the properties of SCB, P k ¼ 1=(a H k R ¡1 a k ) [6,43]. Hence an approximate solution of (31) iŝ P k = a H k R ¡1 ¡ R ¡1 a k (a H k R ¡1 a k ) 2 , k = 1,:::, K: Iterating this equation by building R from the latest estimate of fP k g, we get IAA-APES. This approximation has two advantages. First theP k in (32) is guaranteed to be nonnegative, and it alleviates the need for the procedure in (29). Secondly when fP k g is accurate, the difference P k ¡ 1=(a H k R ¡1 a k ) in (31) is small, as discussed above. When fP k g is inaccurate, however, this difference may not be small, and forcing the difference to zero may provide a better estimate of P k . (IAA-ML tends to work well when the snapshot number is large. It is not considered in the numerical examples because of our focus on cases with few snapshots.) Since IAA-APES can be obtained as a close approximation to IAA-ML, which is locally convergent, IAA-APES is expected to also enjoy local convergence. We have never come across an example where IAA-APES did not converge; however, the search for a convergence proof could be a useful direction for future work.

ACKNOWLEDGMENT
We thank Professor Aaron Lanterman for his useful comments on the revisions of a former version of this paper.


Non-humanlike Spoken Dialogue: A Design Perspective

We propose a non-humanlike spoken dialogue design, which consists of two elements: non-humanlike turn-taking and non-humanlike acknowledgment. Two experimental studies are reported in this paper. The first study shows that the proposed non-humanlike spoken dialogue design is effective for reducing speech collisions. It also presents pieces of evidence that show quick humanlike turn-taking is less important in spoken dialogue system design. The second study supports a hypothesis found in the first study that user preference on response timing varies depending on interaction patterns. Upon receiving these results, this paper suggests a practical design guideline for spoken dialogue systems.

Introduction
Speech and language are owned by humans. Therefore, spoken dialogue researchers tend to pursue a humanlike spoken dialogue. Only a few researchers positively investigate restricted (i.e., non-humanlike) spoken dialogue design such as (Fernández et al., 2007).
Humanlikeness is a very important concept and sometimes it is really useful to design machines / interactions. Machines are, however, not humans. We believe humanlikenss cannot be the dominant factor, or gold-standard, for designing spoken dialogues.
Pursuing humanlikeness has at least five critical problems. (1) Cost: in general, humanlikeness demands powerful and highly functional hardware and software, and highly integrated systems requiring top-grade experts both for development and maintenance. All of them lead to cost overrun.
(2) Performance: sometimes, humanlikeness forces performance to be compromised. For example, achieving quick turn-taking which humans do in daily conversations forces automatic speech recognizers, reasoners, etc. to be compromised to enable severe real-time processing. (3) Applicability: differences in cultures, genders, generations, situations limit the applicability of a humanlike design because it often accompanies a rigid character. For example, Shiwa et al. (2008) succeeded in improving users' impression for slow responses from a robot by using a filler but obviously use of such a filler is limited by social appropriateness. (4) Expectancy: humanlike systems induce too much expectancy of users that they are as intelligent as humans. It will result in disappointments  and may reduce users' willingness to use systems. Keeping high willingness is quite important from the viewpoint of both research (for collecting data from users to improve systems) and business (for continuously selling systems with limited functionality). (5) Risk: Although it is not verified, what is called the uncanny valley (Bartneck et al., 2007) probably exists. It is commonly observed that people hate imperfect humanlike systems.
We try to avoid these problems rather than overcome them. Our position is positively exploring non-humanlike spoken dialogue design. This pa-per focuses on its two elements, i.e., decelerated dialogues as non-humanlike turn-taking and an artificial subtle expression (ASE) as non-humanlike acknowledgment 1 , and presents two experimental studies regarding these two elements. ASEs, defined by the authors in , are simple expressions suitable for artifacts, which intuitively notify users about artifacts' internal states while avoiding the above five problems.
In Section 2, the first study, which was previously reported in , is summarized and shows that the proposed nonhumanlike spoken dialogue design is effective for reducing speech collisions. It also presents pieces of evidence that shows quick humanlike turntaking is less important in designing spoken dialogue systems (SDSs). In Section 3, the second study, which is newly reported in this paper, shows a tendency supporting a hypothesis found in the first study that user preference on response timing varies depending on interaction patterns. Upon receiving the results of the two experiments, a design guideline for SDSs is suggested in Section 4.

Study 1: Reducing Speech Collisions with an Artificial Subtle Expression in a Decelerated Dialogue
An important issue in SDSs is the management of turn-taking. Failures of turn-taking due to systems' end-of-turn misdetection cause undesired speech collisions, which harm smooth communication and degrade system usability. There are two approaches to reducing speech collisions due to end-of-turn misdetection. The first approach is using machine learning techniques to integrate information from multiple sources for accurate end-of-turn detection in early timing. The second approach is to make a long interval after the user's speech signal ends and before the system replies simply because a longer interval means no continued speech comes. As far as the authors know, all the past work takes the first approach (e.g., (Kitaoka et al., 2005;Raux and Eskenazi, 2009)) because the second approach deteriorates responsiveness of SDSs. This choice is based on the presumption that users prefer a responsive system to less responsive systems. The presumption is true in most cases if the sys-1 In this paper, acknowledgment denotes that at the level 1 of the joint action ladder (Clark, 1996), which communicates the listener's identifying the signal presented by the speaker. tem's performance is at human level. However, if the system's performance is below human level, high responsiveness might not be vital or even be harmful. For instance, Hirasawa et al. (1999) reported that immediate overlapping backchannels can cause users to have negative impressions. Kitaoka et al. (2005) also reported that the familiarity of an SDS with backchannels was inferior to that without backchannels due to a small portion of errors even though the overall timing and frequency of backchannels was fairly good (but did not come up to human operators). Technologies are advancing but they are still below human level. We challenge the past work that took the first approach. The second approach is simple and stable against user differences and environmental changes. Moreover, it can afford to employ more powerful but computationally expensive speech processing or to build systems on small devices with limited resources. A concern with this approach is debasement of user experience due to poor responsiveness as stated above. Another issue is speech collisions due to users' followingup utterances such as repetitions. Slow responses tend to induce such collision-eliciting speech.
This section shows the results of the experiment in which participants engaged in hotel reservation tasks with an SDS equipped with an ASE-based acknowledging method, which intuitively notified a user about the system's internal state (processing). The results suggest that the method can reduce speech collisions and provide users with positive impressions. The comparisons of evaluations between systems with a slow reply speed and a moderate reply speed suggest that users of SDSs do not care about slow replies. These results indicate that decelerating spoken dialogues is not a bad idea.

Experiment
System An SDS that can handle a hotel reservation domain was built. The system was equipped with an interface robot with an LED attached to its chest (see Figure 1). Participants' utterances were recognized by an automatic speech recognizer Julius 2 , and interpreted by an in-house language understander. The robot's utterances were voiced by a commercial speech synthesizer. The LCD monitor in Figure 1 was used only to show reservation details at last. Julius output a recognition result to the system at 400 msec after an input speech signal ended, but the system awaited the next input for a fixed interval (wait interval, whose length is given as an experimental factor). If the system received an additional input, it awaited the next input for the same interval again. Otherwise, the system replied.
The LED started blinking at 1/30 sec evenintervals when a speech signal was detected and stopped when the system started replying. The basic function of the blinking light expression is similar to hourglass icons used in GUIs. A big difference is that basically GUIs can ignore any input while they are showing those icons, but SDSs must accept successive speech while it is blinking an LED. What we intend to do is to suppress only collision-eliciting speech such as repetitions (we call them follow-ups) which are negligible but difficult to be automatically distinguished from barge-ins. Barge-ins are not negligible.
Conditions and participants Two experimental factors were set-up, that is, the reply speed factor (moderate or slow reply speed) and the blinking light factor (with or without a blinking light), resulting in four conditions: A: slow reply speed, with a blinking light, B: slow reply speed, without a blinking light, C: moderate reply speed, with a blinking light, D: moderate reply speed, without a blinking light.
We randomly assigned 48 Japanese participants 2 http://julius.sourceforge.jp/ (mean age 30.9) to one of the four conditions.
A reply speed depends on a wait interval for which the dialogue system awaits the next input. Shiwa et al. (2008) showed that the best reply speed for a conversational robot was one second. Thus we chose 800 msec as the wait interval for the moderate reply speed because an actual reply speed was the accumulation of the wait interval and a delay for processing a user request, and 800 msec is simply twice the default length (the VAD tail margin) by which the Julius speech recognizer recognizes the end of a speech. For the slow reply speed, we chose 4 sec as the wait interval. Wait intervals include the VAD tail margin. Figure 2 shows how the system and the LED work along with user speech. In this figure, a user utters a continuous speech with a rather long pause that is longer than the VAD tail margin but shorter than the wait interval. If the system detects the end of the user's turn and starts speaking within the interval marked with an 'X', a speech collision would occur. If the user utters a follow-up within the interval marked with a 'Y', a speech collision would occur, too. We try to suppress the former speech collision by decelerating dialogues and the latter by using a blinking light as an ASE.
Method The experiment was conducted in a room for one participant at one time. Participants entered the room and sat on a chair in front of a desk as shown in Figure 1.
The experimenter gave the participants instructions so as to reserve hotel rooms five times by talking with the robot in front of them. All of them were given the same five tasks which require them to reserve several rooms (one to three) at the same time. The meaning of the blinking light expression was not explained to them. After giving the instructions, the experimenter left the participants, and they began tasks when the robot started to talk to them. Each task was limited to up to three minutes. After finishing the tasks, the participants an-swered a questionnaire. Figure 5 and Figure 6 in the appendix show one of the five task instructions, and a dialogue on that task, respectively.

Results
Reply speeds Averages of observed reply speeds were calculated from the timestamps in transcripts. They were 4.53 sec for the slow conditions and 1.42 sec for the moderate conditions.
Task completion The average number of completed tasks in the four conditions A, B, C, and D were 4.00, 3.83, 3.83, and 4.33, respectively. An ANOVA did not find any significant difference.
Speech collisions We counted speech collisions for which the SDS was responsible, that is, the cases where the robot spoke while participants were talking (i.e., end-of-turn misdetections). Of course, there were speech collisions for which participants were responsible, that is, the cases where participants intentionally spoke while the robot was talking (i.e., barge-ins). These speech collisions were not the targets, hence they were not included in the counts.
Speech collisions due to participants' backchannel feedbacks were not included, either. We think that it is possible to filter out such feedback because feedback utterances are usually very short and variations are small. On the other hand, as we mentioned above, it is not easy to automatically distinguish negligible speech such as repetitions from barge-ins. We want to suppress only such speech negligible but hard to distinguish from other not negligible speech.
The number of observed speech collisions in the four conditions A, B, C, and D were 5, 11, 45, and 30, respectively. First we performed an ANOVA on the number of collisions. The interaction effect was not significant (p = 0.24). A significant difference on the reply speed factor was found (p < 0.005). This result confirms that decelerating dialogues reduces collisions. The effect of the blinking light factor was not significant (p = 0.60).
Next we performed a Fisher's exact test (oneside) on the number of participants who had speech collisions between the two conditions of the slow reply speed (3 out of 12 for A and 8 out of 12 for B). The test found a significant difference (p < 0.05). This result indicates that the blinking light can reduce speech collisions by suppressing users' follow-ups in decelerated dialogues.
Impression on the dialogue and robot The participants rated 38 positive-negative adjective pairs (such as smooth vs. rough) for evaluating both the dialogue and the robot. The ratings are based on a seven-point Likert scale.
An ANOVA found a positive marginal significance (p = 0.07) for the blinking light in the comfortableness factor extracted by a factor analysis for the impression on the dialogue. In addition, an ANOVA found a positive marginal significance (p = 0.07) for the slow reply speed in the modesty factor extracted by a factor analysis for the impression on the robot. Surprisingly, no significant negative effect for the slow reply speed was found.
System evaluations The participants evaluated the SDS in two measures on a scale from 1 to 7, that is, the convenience of the system and their willingness to use the system. The greater the evaluation value is, the higher the degree of convenience or willingness.
The average scores of convenience in the four conditions A, B, C, and D were 3.50, 3.17, 3.17, and 3.92, respectively. Those of willingness were 3.58, 2.58, 2.83, and 3.42, respectively. ANOVAs did not find any significant difference among the four conditions both for the two measures.
Discussion on user preference The analysis of the questionnaire suggests that the blinking light expression gives users a comfortable impression on the dialogue. The analysis also suggests that the slow reply speed gives users a modest impression on the interface robot. Meanwhile, no negative impression with a statistical significance is found on the slow reply speed.
Although no statistically significant difference is found between the four conditions, numbers of completed tasks and convenience are strongly correlated. However, users' willingness to use the systems, which is the most important measure for systems, is inverted between condition A and D. Convenience will be primarily dominated by what degree a user's purpose (reserving rooms) is achieved, thus, it is reasonable that convenience scores correlate with the number of completed tasks. On the other hand, willingness will be dominated by not only practical usefulness but also overall usability or experience. Therefore, we can interpret that the improvements in impressions and reduction in aversive speech collisions let condition A have the highest score for willingness. These results indicate that decelerating spoken dialogues is not a bad idea in contradiction to the common design policy in human-computer interfaces (HCIs), and they suggest to exploit merits provided by decelerating dialogues rather than pursuing quickly responding humanlike systems.
Our finding contradicts not only the common design policy in HCIs but also the design policy in human-robot interaction found by Shiwa et al. (2008), that is, the best response timing of a communication robot is at one second. We think this contradiction is superficial and is ascribable to the following four major differences between their study and our study.
• They adopted a within-subjects experimental design while we adopted a between-subjects design. A within-subjects design makes subjects do relative evaluations and tends to emphasis differences. • Their question was specific in terms of response timing. Our questions were overall ratings of the system such as convenience. • They assumed a perfect machine (Wizard-of-Oz experiment). Our system was elaborately crafted but still far from perfect. • Our system quickly returns non-verbal responses even if verbal responses are delayed.
From these differences, we hypothesize that response timing has no significant impact on the usability of SDSs in an absolute and holistic context at least in the current state of the art spoken dialogue technology, even though users prefer a system which responds quickly to a system which responds slowly when they compare them with each other directly, given an explicit comparison metric on response timing with perfect machines.

Study 2: Uncovering Comfortableness of Response Timing under Different Interaction Patterns
Our conclusion in Section 2 is that SDSs do not need to quickly respond verbally as long as they quickly respond non-verbally by showing their internal states with an ASE, while many researchers try to make them verbally respond as fast as possible. Decelerating a dialogue has many practical advantages as stated above. However, through the experiment, we have also suspected that this conclusion is not valid in some specific cases. That is, we think in some situations users feel uncomfortable with slow verbal responses primordially, and those situations are such as when users simply reply to systems' yes-noquestions or greetings. Our hypothesis is that users expect quick verbal responses (and hate slow verbal responses) only when users expect that it is not difficult for systems to understand their responses or to decide next actions. This section reports the experiment validating this hypothesis.

Experiment
To validate the hypothesis described above, we conducted a Wizard-of-Oz experiment using fixed scenarios. Participants engaged in short interactions with an interface robot and evaluated response timing of the robot. Three experimental factors were interaction patterns, response timing (wait interval), and existence of a blinking light.
Interaction patterns Five interaction patterns were setup to see the differences between situations. Each pattern consisted of three utterances. The first utterance was from the system. Upon receiving the utterance, a participant as a user of the system replied with the second utterance. Then the system responded after the given wait interval (1 sec or 4 sec) with the third utterance. Participants evaluated this interval between the second utterance and the third utterance in a measure of comfortableness.
The patterns with scenarios are shown in Figure 3. They will be referred to by abbreviations (PGG, QYQ, QNQ, PSQ, PLQ) in what follows. Note that the scenarios are originally in Japanese. Here, RequestS and RequestL mean a short request and a long request, respectively. YNQuestion and WhQuestion mean a yes-no-question and a wh-question, respectively. According to the hypothesis, we can predict that the reported comfortableness for the longer wait interval (4 sec) are worse for short and formulaic cases such as PGG and QYQ than for the long request case (i.e., PLQ). In addition, we can predict that the reported comfortableness for longer intervals improves for PLQ if the robot's light blinks, while that does not improve for PGG and QYQ.
System We used the same interface robot and the LCD monitor as study 1. The experiment in this study, however, was conducted using a WOZ system. S: Welcome to our Hotel. May I help you? U: I would like to reserve rooms with breakfast from tomorrow, one single room and one double room, nonsmoking and smoking, respectively. S: How long will you stay? Figure 3: Interaction patterns and scenarios First the WOZ system presents an instruction to the participant on the LCD monitor, which reveals the robot's first utterance of the given scenario (e.g., "Welcome to our Hotel. May I help you?") and indicates the participant's second utterance (e.g., "Hello."). Two seconds after the participant clicks the OK button on the monitor with a computer mouse, the system makes the robot utter the first utterance. Then, the participant replies, and the operator of the system end-points the end of participant's speech by clicking a button shown in another monitor for the operator in the room next to the participant's room. After the end-pointing, the system waits for the wait interval (one second or four seconds) and makes the robot utter the third utterance of the scenario. One second after, the system asks the participant to evaluate the comfortableness of the response timing of the robot's third utterance on a scale from 1 to 7 (1:very uncomfortable, 4:neutral, 7:very comfortable) on the LCD monitor.
Conditions and participants Forty participants (mean age 28.8, 20 males and 20 females) engaged in the experiment. No participant had engaged in study 1. They were randomly assigned to one of two groups (gender was balanced). The groups correspond to one of two levels of the experimental factor of the existence of a blinking light. For one group, the robot blinked its LED when it was waiting. For the other group, the robot did not blink the LED. We refer to the former group (condition) as BL (Blinking Light, n=20) and the later as NL (No Light,n=20). In summary, this experiment is within-subjects design with regard to interaction patterns and response timing and is between-subjects design with regard to the blinking light.
Method The experiment was conducted in a room for one participant at one time. Participants entered the room and sat on a chair in front of a desk as shown in Figure 1, but they did not wear headphones this time.
The experimenter gave the participants instructions so as to engage in short dialogues with the robot in front of them. They engaged in each of five scenarios shown in Figure 3 six times (three times with a 1 sec wait interval and three with 4 sec), resulting in 30 dialogues (5 × 3 × 2 = 30). The order of scenarios and intervals was randomized. The existence and meaning of the blinking light expression was not explained to them. They were not told that the system was operated by a human operator, either. After giving the instructions, the experimenter left the participants, and they practiced one time. This practice used a Prompt-RequestM-WhQuestion 3 type scenario with a wait interval of two seconds. Then, thirty dialogues were performed. Short breaks were inserted after ten dialogues. Each dialogue proceeded as explained above.

Results
End-pointing errors End-pointing was done by a fixed operator. We obtained 1,184 dialogues out of 1,200 (= 30 × 40) after removing dialogues in which end-pointing failed (failures were selfreported by the operator). We sampled 30 dialogues from the 1,184 dialogues and analyzed endpointing errors in the recorded speech data. The average error was 84.6 msec (SD=89.6).
Comfortableness This experiment was designed to grasp a preliminary sense on our hypothesis as much as possible with a limited number of participants in exchange for abandonment of use of statistical tests, because this study involved multiple factors and the interaction pattern factor was complex by itself. Therefore, in the following discussion on comfortableness, we do not refer to statistical significances.  Table 1). The X axes in the graphs correspond to response timing, that is, the two wait intervals of 1 sec and 4 sec. The Y axes correspond to comfortableness reported in a scale from 1 to 7. Obviously, with or without a blinking light effected comfortableness.
The results shown in the graphs support the predictions made in Section 3.1. The scores of PGG and QYQ are worse than that of PLQ at 4 sec. PGG and QYQ show no difference between NL and BL. QNQ and PSQ show differences. PLQ shows the biggest difference. In case of PLQ, the reported comfortableness at 4 sec shifted to almost the neutral position (score 4) by presenting a blinking light. This indicates that a blinking light ASE can allay the debasement of impression due to slow responses only in non-formulaic cases.
Interestingly, the blinking light expression attracted comfortableness scores to neutral both at 1 sec and at 4 sec. We can make two hypotheses on this result. One is that the blinking light expression has a negative effect which degrades comfortableness at 1 sec. The other is that the blinking light expression makes participants difficult to see differences between 1 sec and 4 sec, therefore, reported scores converge to neutral. At this stage we think that the later is more probable than the former because the scores of PGG and QYQ should be degraded at 1 sec if the former is true.

A Practical Design Guideline for SDSs
Summarizing the results of the experiments presented in Section 2 and Section 3, we suggest a twofold design guideline for SDSs, especially for task-oriented systems. Some interaction-oriented systems such as chatting systems are out of scope of this guideline. In what follows, first the guideline is presented and then a commentary on the guideline is described.
The guideline (1) Never be obsessed with quick turn-taking but acknowledge users immediately Quick turn-taking will not recompense your efforts, resources inputted, etc. Pursue it only after accomplishing all you can do without compromising performance in other elements of dialogue systems and only if it does not make system development and maintenance harder. However, quick (possibly non-verbal) acknowledgment is a requisite. You can compensate for the debasement of user experience due to slow verbal responses just by using an ASE such as a tiny blinking LED to acknowledge user speech. No instruction about the ASE is needed for users.
(2) Think of users' expectations Users expect rather quick verbal responses to their greetings and yes-answers. ASEs will be ineffective for them. Thus it is recommended to enable your systems to quickly respond verbally to such utterances. Fortunately it is easy to anticipate such utterances. Greetings usually occur only at the beginning of dialogues or after tasks were accomplished. Yes-answers will come only after yes-noquestions. Therefore it will be able to implement an SDS that quickly responds verbally to greeting and yes-answers both without increasing development / maintenance costs and without decreasing recognition performance, etc.
However, you should keep in mind that too quick verbal responses (0 sec interval or overlapping) may not be welcomed (Hirasawa et al., 1999;Shiwa et al., 2008). They may also induce too much expectancy in users and result in disappointments to your systems after some interactions.

Commentary on the guideline
The guideline was constructed so as to avoid the five problems pointed out in Section 1. The first point of the guideline is induced mainly from the results of study 1, and the second point is induced mainly from the results of study 2.
Although the results of study 2 indicate users prefer quick responses to slow ones as presupposed in past literature, note that the experiment in study 2 is within-subjects design with regard to the response timing factor and that within-subjects design tends to emphasis differences as discussed at the end of Section 2. The results of study 1 suggested that such an emphasized difference (i.e., preference for quick responses) has no significant impact on the usability of SDSs on the whole.

Conclusion
This paper proposed a non-humanlike spoken dialogue design, which consists of two elements: non-humanlike turn-taking and acknowledgment. Two experimental studies were reported regarding these two elements. The first study showed that the proposed non-humanlike spoken dialogue design is effective for reducing speech collisions. This study also presented pieces of evidence that show quick humanlike turn-taking is less important in spoken dialogue system (SDS) design. The second study showed a tendency supporting a hypothesis found in the first study that user preference on response timing varies depending on interaction patterns in terms of comfortableness. Upon receiving these results, a practical design guideline for SDSs was suggested, that is, (1) never be obsessed with quick turn-taking but acknowledge users immediately and (2) think of users' expectations.
Our non-humanlike acknowledging method using an LED-based artificial subtle expression (ASE) can apply to any interfaces on wearable / handheld devices, vehicles, whatever. It is, however, difficult to directly apply it to call-centers (i.e., telephone interfaces), which occupy a big portion of the deployed SDSs pie. Yet, the underlying concept: decelerated dialogues accom-panied by an ASE will be applicable even to telephone interfaces by using an auditory ASE, which is to be explored in future work.
The guideline is supported by findings in a rather hypothetical stage. More experiments are necessary to confirm these findings. In addition, the guideline is for the current transitory period in which intelligence technologies such as automatic recognition, language processing, reasoning etc. are below human level. In that sense, the contribution of this paper might be limited. However, this period will last until a decisive paradigm shift occurs in intelligence technologies. It may come after a year, a decade, or a century.