Introduction
Model Predictive Path Integral control (MPPI) [1 ] , [2 ] is a sampling-based Model Predictive Control (MPC) method. It updates the input by a weighted average of randomly generated input sequences, with exponential weights determined by the cost of each input sequence. MPPI has several advantages. Since MPPI requires no cost gradients, it directly handles nonlinear dynamics and non-convex or discontinuous costs. Since the computations for individual samples are independent, MPPI is implemented efficiently on GPUs. Furthermore, the input is updated using a weighted average of all samples, allowing information from the entire sample set to contribute to the update, unlike the random shooting method [3 ] and the cross-entropy method [4 ] . Hence the computed input sequence tends to be smoother than those of these methods. Owing to these advantages, MPPI has been applied to various control problems including whole-body control of legged robots [5 ] , navigation of ground robots in cluttered and off-road environments [6 ] , [7 ] , agile flight and navigation of quadrotors [8 ] , [9 ] , aggressive driving on dirt tracks [10 ] , [11 ] , off-road driving over uneven terrain [12 ] , [13 ] , and motion planning for autonomous driving [14 ] .
MPPI still has two open issues. One is the degradation of control performance with longer prediction horizons. Since MPPI samples input sequences over the prediction horizon, the search dimension grows linearly with the prediction horizon. Hence, when limited computational resources prevent increasing the number of samples, extending the horizon makes the samples sparse in the search space due to the curse of dimensionality [15 ] , [16 ] and degrades control performance. In addition, when the number of samples is small relative to the search dimension, high-frequency components remain in the computed input and cause chattering and actuator wear [17 ] . Existing studies on this issue fall broadly into three categories: methods that design the sampling distribution to increase the number of effective samples [11 ] , [18 ] –[20 ] , methods that modify how samples are drawn without changing the distribution [21 ] , [22 ] , and methods that reduce the search dimension itself [5 ] , [23 ] .
The other issue for MPPI is the lack of theoretical guarantees, in particular stability and performance analysis for the closed-loop system. Existing research has focused on the evaluation of the sampling error [24 ] , the convergence analysis of the optimization method [25 ] , and the increase in free energy caused by constraint violations or imperfect tracking performance [11 ] . The stability of the closed-loop system is regarded as an open problem [26 ] . Yoon and Kim [27 ] treated finite-sample MPPI for linear systems as a perturbation of LQR and showed practical exponential stability in expectation. The number of samples required for their theory to hold remains unclear.
This paper develops a new control algorithm that reduces the search dimension of MPPI using Laguerre basis functions. We then analyze the stability of the resulting closed-loop system and the sampling accuracy with a finite number of samples. Laguerre basis functions form a discrete-time orthonormal basis and have been used in system identification [28 ] and in MPC to reduce the number of optimization variables [29 ] . Motivated by their use in MPC, we propose Laguerre-MPPI, which represents the sampled input of MPPI with Laguerre basis functions. Since Laguerre-MPPI samples the coefficients of the Laguerre basis instead of the input sequence, its search dimension is independent of the prediction horizon. Hence, extending the prediction horizon does not require more samples to maintain the sampling density. We derive a stability condition for the infinite-sample closed-loop system and show that closed-loop stability can be lost depending on the basis selection. To evaluate the sampling error under finite samples, we present the closed form of the covariance of the sampling error and the limit of the ratio of the effective sample size (ESS) to the number of samples. Based on these expressions, we provide a guideline on the number of samples required for the theory to hold, and show that the maximum of the asymptotic ESS ratio of Laguerre-MPPI over the initial estimate coefficient is no less than that of conventional MPPI.
The contributions of this paper are as follows.
We expand the input in Laguerre basis functions and develop Laguerre-MPPI (Section III).
For linear systems with quadratic costs, we translate the closed-loop behavior into the behavior of a stochastic dynamical system to derive the stability condition in the infinite-sample limit (Section IV).
We derive the asymptotic covariance of the sampling error and the asymptotic ESS ratio in closed form, and give a lower bound on the number of samples. We then show that, regardless of the basis selection, the maximum of the asymptotic ESS ratio of Laguerre-MPPI over the initial estimate coefficient is no less than that of conventional MPPI (§ 10 ).
Notation: The m × m m \times m m × m identity matrix is denoted by I m I_m I m , the Kronecker product by ⊗ \otimes ⊗ , the vector obtained by stacking the columns of a matrix by vec ( ⋅ ) \operatorname{vec}(\cdot) vec ( ⋅ ) , the spectral radius by ρ ( ⋅ ) \rho(\cdot) ρ ( ⋅ ) , the Kronecker delta by δ i j \delta_{ij} δ ij , and the inverse z z z -transform by Z − 1 Z^{-1} Z − 1 . For a square matrix X X X , its determinant is denoted by ∣ X ∣ |X| ∣ X ∣ , and its positive definiteness (positive semidefiniteness) by X ≻ 0 X \succ0 X ≻ 0 (X ⪰ 0 X \succeq0 X ⪰ 0 ). For a vector z z z and a matrix Q Q Q , the weighted squared norm is defined by ∥ z ∥ Q 2 : = z T Q z \lVert z\rVert_Q^2 := z^{\mathsf{T}}Qz ∥ z ∥ Q 2 := z T Q z . We denote by N ( μ , Σ ) \mathcal{N}(\mu,\Sigma) N ( μ , Σ ) the Gaussian distribution with mean μ \mu μ and covariance Σ \Sigma Σ , and by E F [ ⋅ ] \mathbb{E}_{F}[\cdot] E F [ ⋅ ] and Cov F [ ⋅ ] \operatorname{Cov}_{F}[\cdot] Cov F [ ⋅ ] the expectation and the covariance matrix with respect to a distribution F F F . The probability density function of a distribution is denoted by the corresponding lowercase letter. The Kullback–Leibler divergence is defined by D K L ( F ∥ H ) : = ∫ f ln ( f / h ) d X D_{\mathrm{KL}}(F\Vert H) := \int f \ln(f/h)\,\mathrm{d}X D KL ( F ∥ H ) := ∫ f ln ( f / h ) d X . Convergence in distribution is denoted by → d \xrightarrow{\mathrm{d}} d , and almost sure convergence by a.s.
PRELIMINARIES: MPPI
Before presenting Laguerre-MPPI, we review the theory of MPPI on which it is built, following the information-theoretic derivation of Williams et al. [2 ] .
Stochastic Optimal Control Problem
Consider a general discrete-time system of the form
x ( k + 1 ) = F ( x ( k ) , v ( k ) ) , x ( 0 ) = x 0 , (1) x(k+1) = F(x(k),v(k)), \qquad x(0) = x_0, \tag*{(1)} x ( k + 1 ) = F ( x ( k ) , v ( k )) , x ( 0 ) = x 0 , (1)
where x ( k ) ∈ R n x(k) \in\mathbb{R}^{n} x ( k ) ∈ R n is the state, v ( k ) ∈ R m v(k) \in\mathbb{R}^{m} v ( k ) ∈ R m is the sampled input, and F : R n × R m → R n F:\mathbb{R}^{n} \times\mathbb{R}^{m} \to\mathbb{R}^{n} F : R n × R m → R n represents the system dynamics. The sampled input sequence up to the prediction horizon T T T is denoted by
V : = [ v ( 0 ) ⋯ v ( T − 1 ) ] ∈ R m × T . (2) V := [v(0)\ \cdots\ v(T-1)] \in\mathbb{R}^{m \times T}. \tag*{(2)} V := [ v ( 0 ) ⋯ v ( T − 1 )] ∈ R m × T . (2)
The sampled input sequence V V V is a random variable, and its columns v ( k ) v(k) v ( k ) independently follow the Gaussian distribution N ( u ( k ) , Σ v ) \mathcal{N}(u(k),\Sigma_v) N ( u ( k ) , Σ v ) , with the mean input u ( k ) u(k) u ( k ) and covariance matrix Σ v ≻ 0 \Sigma_v \succ0 Σ v ≻ 0 . The mean input sequence is denoted by
U : = [ u ( 0 ) ⋯ u ( T − 1 ) ] ∈ R m × T . U := [u(0)\ \cdots\ u(T-1)] \in\mathbb{R}^{m \times T}. U := [ u ( 0 ) ⋯ u ( T − 1 )] ∈ R m × T .
Furthermore, we define the distribution of the sampled input sequence V V V by Q U : = N ( U , Σ v ) \mathbb{Q}_{U} := \mathcal{N}(U,\Sigma_v) Q U := N ( U , Σ v ) , in which the columns v ( k ) v(k) v ( k ) independently follow N ( u ( k ) , Σ v ) \mathcal{N}(u(k),\Sigma_v) N ( u ( k ) , Σ v ) , and call it the control distribution. The same notation is used for the other distributions of the sampled input sequence.
To derive the MPPI algorithm, we address the following stochastic optimal control problem.
Problem 1 (Stochastic Optimal Control):
min U ∈ U E Q U [ ϕ ( x ( T ) ) + ∑ k = 0 T − 1 L k ( x ( k ) , u ( k ) ) ] , (3) \min_{U \in\mathcal{U}} \mathbb{E}_{\mathbb{Q}_{U}}\left[\phi(x(T))+\sum_{k=0}^{T-1}\mathcal{L}_k(x(k),u(k))\right], \tag*{(3)} U ∈ U min E Q U [ ϕ ( x ( T )) + k = 0 ∑ T − 1 L k ( x ( k ) , u ( k )) ] , (3)
where ϕ ( x ( T ) ) \phi(x(T)) ϕ ( x ( T )) is the terminal cost, L k ( x ( k ) , u ( k ) ) \mathcal{L}_k(x(k),u(k)) L k ( x ( k ) , u ( k )) is the stage cost of the state and input, and U \mathcal{U} U is the feasible set of the mean input sequence U U U .
Since this problem is intractable due to the implicit form of U U U , we consider an approximation of it. We impose the following assumption.
Assumption 1: The stage cost L k ( x ( k ) , u ( k ) ) \mathcal{L}_k(x(k),u(k)) L k ( x ( k ) , u ( k )) is
L k ( x ( k ) , u ( k ) ) = c k ( x ( k ) ) + b k ( u ( k ) ) , \mathcal{L}_k(x(k),u(k)) = c_k(x(k)) + b_k(u(k)), L k ( x ( k ) , u ( k )) = c k ( x ( k )) + b k ( u ( k )) , where c k ( x ( k ) ) c_k(x(k)) c k ( x ( k )) is the state cost, and b k ( u ( k ) ) b_k(u(k)) b k ( u ( k )) is the input cost.
For brevity, we collect the state costs in (3) as
S ( V ) : = ϕ ( x ( T ) ) + ∑ k = 0 T − 1 c k ( x ( k ) ) . (4) S(V) := \phi(x(T))+\sum_{k=0}^{T-1}c_k(x(k)). \tag*{(4)} S ( V ) := ϕ ( x ( T )) + k = 0 ∑ T − 1 c k ( x ( k )) . (4)
The state cost S : R m × T → R S:\mathbb{R}^{m \times T} \to\mathbb{R} S : R m × T → R returns the cost of the trajectory generated from the sampled input sequence V V V . Furthermore, we introduce the reference distribution Q ~ : = N ( U ~ , Σ v ) \widetilde{\mathbb{Q}} := \mathcal{N}(\widetilde{U},\Sigma_v) Q := N ( U , Σ v ) with the reference input sequence U ~ \widetilde{U} U , to which the control distribution Q U \mathbb{Q}_{U} Q U refers.
Free Energy and Relaxed Stochastic Optimal Control Problem
To solve (3)`` approximately, we introduce the free energy [30 ] .
Definition 1 (Free energy): The following quantity is called the free energy of the control system composed of (1) and (3):
F ( S , q ~ , λ ) : = − λ ln ( E Q ~ [ exp ( − S ( V ) λ ) ] ) , (5) \mathcal{F}(S,\widetilde{q},\lambda) := -\lambda\ln\left(\mathbb{E}_{\widetilde{\mathbb{Q}}}\left[\exp\left(-\frac{S(V)}{\lambda}\right)\right]\right), \tag*{(5)} F ( S , q , λ ) := − λ ln ( E Q [ exp ( − λ S ( V ) ) ] ) , (5)
where λ ∈ R + \lambda\in\mathbb{R}^{+} λ ∈ R + is called the temperature parameter.
Throughout this paper, we assume that the expectation in (5) is finite, which holds, e.g., when the state cost S S S is bounded below.
We show that the free energy F \mathcal{F} F is a lower bound of some cost function. To this end, we introduce an arbitrary probability distribution Q \mathbb{Q} Q of the sampled input sequence V V V . Then, the following lemma holds.
Lemma 1: For any distribution Q \mathbb{Q} Q , the following inequality holds:
F ( S , q ~ , λ ) ≤ E Q [ S ( V ) ] + λ D K L ( Q ∥ Q ~ ) . (6) \mathcal{F}(S,\widetilde{q},\lambda) \leq\mathbb{E}_{\mathbb{Q}}[S(V)] + \lambda D_{\mathrm{KL}}(\mathbb{Q}\Vert\widetilde{\mathbb{Q}}). \tag*{(6)} F ( S , q , λ ) ≤ E Q [ S ( V )] + λ D KL ( Q ∥ Q ) . (6)
Proof: See Appendix A (see also [2 ] ). ■
The first term on the right-hand side is the expected state cost, and the second term represents the discrepancy between the arbitrary distribution and the reference distribution through their KL divergence. Intuitively, the first term is interpreted as a state cost and the second term as an input cost. Hence, we let
J ( Q ) : = E Q [ S ( V ) ] + λ D K L ( Q ∥ Q ~ ) . (7) J(Q) := \mathbb{E}_{Q}[S(V)] + \lambda D_{\mathrm{KL}}(Q\Vert\widetilde{Q}). \tag*{(7)} J ( Q ) := E Q [ S ( V )] + λ D KL ( Q ∥ Q ) . (7)
Note that the cost function J ( Q ) J(Q) J ( Q ) is defined for an arbitrary distribution Q Q Q , not only for Gaussian distributions. To clarify the relation between the cost function J ( Q ) J(Q) J ( Q ) and the objective function of Problem 1, we first impose the following assumption.
Assumption 2: The input cost b k ( u ( k ) ) b_k(u(k)) b k ( u ( k )) is a quadratic function of the mean input u ( k ) u(k) u ( k ) given by
b k ( u ( k ) ) = λ 2 ( u ( k ) − u ~ ( k ) ) T Σ v − 1 ( u ( k ) − u ~ ( k ) ) . (8) b_k(u(k)) = \frac{\lambda}{2}(u(k)-\widetilde{u}(k))^{\mathsf{T}}\Sigma_v^{-1}(u(k)-\widetilde{u}(k)). \tag*{(8)} b k ( u ( k )) = 2 λ ( u ( k ) − u ( k ) ) T Σ v − 1 ( u ( k ) − u ( k )) . (8) With this preparation, the following lemma shows that (7) equals the cost function of (3).
Lemma 2: In the cost function J ( Q ) J(Q) J ( Q ) , let the reference distribution be Q ~ = N ( U ~ , Σ v ) \widetilde{Q}=\mathcal{N}(\widetilde{U},\Sigma_v) Q = N ( U , Σ v ) , and set the arbitrary distribution Q Q Q to the control distribution Q U = N ( U , Σ v ) Q_U=\mathcal{N}(U,\Sigma_v) Q U = N ( U , Σ v ) . Under Assumptions 1 and 2, the following equation holds:
J ( Q U ) = E Q U [ ϕ ( x ( T ) ) + ∑ k = 0 T − 1 L k ( x ( k ) , u ( k ) ) ] . J(Q_U)=\mathbb{E}_{Q_U}\left[\phi(x(T))+\sum_{k=0}^{T-1}\mathcal{L}_k(x(k),u(k))\right]. J ( Q U ) = E Q U [ ϕ ( x ( T )) + k = 0 ∑ T − 1 L k ( x ( k ) , u ( k )) ] . Proof: See Appendix B (see also [2 ] ). ■
As stated in Lemma 2, Problem 1 is equivalently reduced to the following optimization problem over the set of control distributions G : = { N ( U , Σ v ) ∣ U ∈ U } \mathcal{G}:=\{\mathcal{N}(U,\Sigma_v)\mid U\in\mathcal{U}\} G := { N ( U , Σ v ) ∣ U ∈ U } as
min U ∈ U E Q U [ ϕ ( x ( T ) ) + ∑ k = 0 T − 1 L k ( x ( k ) , u ( k ) ) ] = min Q ∈ G J ( Q ) . (9) \min_{U\in\mathcal{U}}\mathbb{E}_{Q_U}\left[\phi(x(T))+\sum_{k=0}^{T-1}\mathcal{L}_k(x(k),u(k))\right]=\min_{Q\in\mathcal{G}}J(Q). \tag*{(9)} U ∈ U min E Q U [ ϕ ( x ( T )) + k = 0 ∑ T − 1 L k ( x ( k ) , u ( k )) ] = Q ∈ G min J ( Q ) . (9)
By further removing the constraint Q ∈ G Q\in\mathcal{G} Q ∈ G , we formulate the following stochastic optimal control problem, which is a relaxation of (9):
Problem 2 (Relaxed Stochastic Optimal Control):
Q ∗ = argmin Q J ( Q ) Q^*=\mathop{\operatorname{argmin}}_{Q}J(Q) Q ∗ = argmin Q J ( Q )
Problem 2 is a variational problem of finding the distribution that attains the minimum cost without restricting the form of the distribution. Since the feasible set expands from the set G \mathcal{G} G of control distributions to all distributions, the following inequality holds between Problem 2 and the original Problem 1:
min Q J ( Q ) ≤ min U ∈ U E Q U [ ϕ ( x ( T ) ) + ∑ k = 0 T − 1 L k ( x ( k ) , u ( k ) ) ] . \min_Q J(Q)\leq\min_{U\in\mathcal{U}}\mathbb{E}_{Q_U}\left[\phi(x(T))+\sum_{k=0}^{T-1}\mathcal{L}_k(x(k),u(k))\right]. Q min J ( Q ) ≤ U ∈ U min E Q U [ ϕ ( x ( T )) + k = 0 ∑ T − 1 L k ( x ( k ) , u ( k )) ] .
Optimal Distribution
This subsection gives the solution of Problem 2 through the following lemma.
Lemma 3: The distribution Q ∗ Q^* Q ∗ with the probability density function
q ∗ ( V ) : = 1 η exp ( − S ( V ) λ ) q ~ ( V ) (10) q^*(V):=\frac{1}{\eta}\exp\left(-\frac{S(V)}{\lambda}\right)\widetilde{q}(V) \tag*{(10)} q ∗ ( V ) := η 1 exp ( − λ S ( V ) ) q ( V ) (10) is the unique solution of Problem 2, where η \eta η is the normalization constant and is defined by
η : = ∫ R m × T exp ( − S ( V ) λ ) q ~ ( V ) d V (11) \eta:=\int_{\mathbb{R}^{m\times T}}\exp\left(-\frac{S(V)}{\lambda}\right)\widetilde{q}(V)\,dV \tag*{(11)} η := ∫ R m × T exp ( − λ S ( V ) ) q ( V ) d V (11) = E Q ~ [ exp ( − S ( V ) λ ) ] . =\mathbb{E}_{\widetilde{Q}}\left[\exp\left(-\frac{S(V)}{\lambda}\right)\right]. = E Q [ exp ( − λ S ( V ) ) ] . In addition, J ( Q ∗ ) = F ( S , q ~ , λ ) J(Q^*)=F(S,\widetilde{q},\lambda) J ( Q ∗ ) = F ( S , q , λ ) holds.
Proof: See Appendix C (see also [2 ] ). ■
Hereafter, we call the distribution Q ∗ Q^* Q ∗ , given by (10), the optimal distribution. As (10) shows, the optimal distribution Q ∗ Q^* Q ∗ has a complex shape even when the reference distribution is Gaussian, Q ~ = N ( U ~ , Σ v ) \widetilde{Q}=\mathcal{N}(\widetilde{U},\Sigma_v) Q = N ( U , Σ v ) .
Minimization of KL Divergence
A drawback of the optimal distribution Q ∗ Q^* Q ∗ , characterized by (10), is that it is computationally intractable in general. Moreover, Q ∗ Q^* Q ∗ is generally non-Gaussian and therefore cannot be recovered by restricting the search to the Gaussian control distributions Q U = N ( U , Σ v ) Q_U=\mathcal{N}(U,\Sigma_v) Q U = N ( U , Σ v ) . Our goal is therefore to approximate Q ∗ Q^* Q ∗ by Q U Q_U Q U , which is obtained by minimizing the KL divergence between Q U Q_U Q U and Q ∗ Q^* Q ∗ .
Problem 3 (KL Divergence Minimization):
U ∗ = argmin U ∈ U D K L ( Q ∗ ∥ Q U ) (12) U^*=\mathop{\operatorname{argmin}}_{U\in\mathcal{U}}D_{\mathrm{KL}}(Q^*\Vert Q_U) \tag*{(12)} U ∗ = argmin U ∈ U D KL ( Q ∗ ∥ Q U ) (12)
When U = R m × T \mathcal{U}=\mathbb{R}^{m\times T} U = R m × T , Problem 3 is solvable in closed form, and the optimal input sequence U ∗ U^* U ∗ in (12) is given by
U ∗ = E Q ∗ [ V ] . (13) U^*=\mathbb{E}_{Q^*}[V]. \tag*{(13)} U ∗ = E Q ∗ [ V ] . (13)
The key implication of (13) is that the optimal approximation to Q ∗ Q^* Q ∗ within the family of control distributions N ( U , Σ v ) \mathcal{N}(U,\Sigma_v) N ( U , Σ v ) is determined solely by the mean of Q ∗ Q^* Q ∗ . Hence, the optimal input sequence U ∗ U^* U ∗ , the mean of the distribution Q U Q_U Q U that approximates Q ∗ Q^* Q ∗ , is obtained by performing the integral:
U ∗ = 1 η ∫ R m × T V exp ( − S ( V ) λ ) q ~ ( V ) d V . (14) U^*=\frac{1}{\eta}\int_{\mathbb{R}^{m\times T}}V\exp\left(-\frac{S(V)}{\lambda}\right)\widetilde{q}(V)\,dV. \tag*{(14)} U ∗ = η 1 ∫ R m × T V exp ( − λ S ( V ) ) q ( V ) d V . (14)
Note that the state cost S ( V ) S(V) S ( V ) , defined in (4), is a complicated function and the integral is high-dimensional. A promising approach to (14) is the use of sampling, that is, computing the expectation in (13) by generating sampled input sequences that follow the optimal distribution Q ∗ Q^* Q ∗ . In the next subsection, we introduce an approach by importance sampling.
Algorithm 1 MPPI
Require: $M$, $T$, $\lambda$, $\Sigma_v$, $\tilde{U}$, $\hat{U}$
1: for $k = 0,1,2,\ldots$ do
2: Generate $\{V^i\}_{i=1}^{M}$ from $\hat{Q} = \mathcal{N}(\hat{U},\Sigma_v)$
3: for $i = 1,\ldots,M$ do
4: Apply $V^i$ to (1) and compute $S(V^i)$
5: Compute $w(V^i)$ by (16)
6: end for
7: $U^\dagger \leftarrow \frac{\sum_{i=1}^{M}w(V^i)V^i}{\sum_{i=1}^{M}w(V^i)}$
8: Apply the first column $u^\dagger(0)$ of $U^\dagger$ to the system
9: Update $\hat{U}$
10: end for
Importance Sampling
Although no method is available for generating the sampled input sequence V V V from Q ∗ Q^* Q ∗ , the functional form exp ( − S ( V ) λ ) q ~ ( V ) \exp\left(-\frac{S(V)}{\lambda}\right)\tilde{q}(V) exp ( − λ S ( V ) ) q ~ ( V ) is known. Hence importance sampling is applicable. We therefore introduce a known initial estimate distribution Q ^ \hat{Q} Q ^ from which the sampled input sequence V V V is readily generated. The following theorem presents an alternative expression of U ∗ U^* U ∗ , given in (13).
Theorem 1: Let the initial estimate distribution and the reference distribution be given by Q ^ = N ( U ^ , Σ v ) \hat{Q}=\mathcal{N}(\hat{U},\Sigma_v) Q ^ = N ( U ^ , Σ v ) and Q ~ = N ( U ~ , Σ v ) \tilde{Q}=\mathcal{N}(\tilde{U},\Sigma_v) Q ~ = N ( U ~ , Σ v ) , respectively. Then, the optimal input sequence U ∗ U^* U ∗ , given in (13), is expressed with the weight w ( V ) w(V) w ( V ) as
U ∗ = E Q ^ [ w V ] E Q ^ [ w ] , (15) U^*=\frac{\mathbb{E}_{\hat{Q}}[wV]}{\mathbb{E}_{\hat{Q}}[w]}, \tag*{(15)} U ∗ = E Q ^ [ w ] E Q ^ [ w V ] , (15) w ( V ) : = exp ( − S ( V ) λ − ∑ k = 0 T − 1 ( u ^ ( k ) − u ~ ( k ) ) ⊤ Σ v − 1 v ( k ) ) . (16) w(V):=\exp\left(-\frac{S(V)}{\lambda}-\sum_{k=0}^{T-1}(\hat{u}(k)-\tilde{u}(k))^\top\Sigma_v^{-1}v(k)\right). \tag*{(16)} w ( V ) := exp ( − λ S ( V ) − k = 0 ∑ T − 1 ( u ^ ( k ) − u ~ ( k ) ) ⊤ Σ v − 1 v ( k ) ) . (16)
Proof: See Appendix D (see also [2 ] ). ■
Since Q ^ \hat{Q} Q ^ is known and the weight w w w is computable, we evaluate (15) by drawing samples from Q ^ \hat{Q} Q ^ and thereby compute the optimal input sequence U ∗ U^* U ∗ in (13) indirectly.
To summarize this section, the original stochastic control problem, stated as Problem 1, is approximated by Problem 3. MPPI provides an efficient method for solving Problem 3 by computing a sample-based approximation of the solution characterized by Theorem 1. The detailed procedure is summarized in Algorithm 1. The input sequence U † U^\dagger U † obtained using a finite number of samples approximates the optimal solution U ∗ U^* U ∗ of Problem 3, given in (15).
Finally, we present a remark that motivates the main results developed in the subsequent sections. The search space of MPPI is m T mT m T -dimensional, which grows linearly with the prediction horizon T T T . For a fixed number of samples M M M , extending the horizon makes the samples increasingly sparse in this space, leading to degraded control performance. To address this issue, Section III proposes a control method whose search dimension is independent of T T T . Section V quantifies this degradation using the ESS.
Laguerre-MPPI and Algorithm
To mitigate the performance degradation of MPPI over long prediction horizons, we expand the control input in Laguerre basis functions. Instead of drawing the sampled input sequence V V V directly, we generate it from coefficients drawn in the coefficient space, whose dimension is independent of the prediction horizon T T T . Section III-A introduces the Laguerre basis functions, and Section III-B expands the input in the basis and derives the linear relationship between the coefficients and the inputs. Section III-C formulates the stochastic optimal control problem in the coefficient space, reconstructs the theory of MPPI in that space, and gives the algorithm of Laguerre-MPPI. Section III-D shows that the algorithm of Laguerre-MPPI reduces to that of MPPI when the covariance matrix in the coefficient space satisfies a specific condition. Section III-E compares Laguerre-MPPI with related studies.
Discrete-Time Laguerre Basis Functions
The discrete-time Laguerre basis functions with pole a ∈ [ 0 , 1 ) a\in[0,1) a ∈ [ 0 , 1 ) are defined by the z z z -transform [28 , 31 ]
Γ i ( z ) : = 1 − a 2 z − a ( 1 − a z z − a ) i − 1 , (17) \Gamma_i(z):=\frac{\sqrt{1-a^2}}{z-a}\left(\frac{1-az}{z-a}\right)^{i-1}, \tag*{(17)} Γ i ( z ) := z − a 1 − a 2 ( z − a 1 − a z ) i − 1 , (17)
where i ∈ { 1 , 2 , … } i\in\{1,2,\ldots\} i ∈ { 1 , 2 , … } is the order of the basis function. Since the all-pass factor has unit magnitude on the unit circle, all basis functions share the magnitude response ∣ Γ i ( e j ω ) ∣ = 1 − a 2 / ∣ e j ω − a ∣ \left|\Gamma_i(e^{j\omega})\right|=\sqrt{1-a^2}/\left|e^{j\omega}-a\right| Γ i ( e j ω ) = 1 − a 2 / e j ω − a , which has low-pass characteristics for any pole a > 0 a>0 a > 0 . We define the basis functions in the time domain as
l i ( k ) : = Z − 1 [ z Γ i ( z ) ] . (18) l_i(k):=\mathcal{Z}^{-1}[z\Gamma_i(z)]. \tag*{(18)} l i ( k ) := Z − 1 [ z Γ i ( z )] . (18)
Parseval’s theorem and the all-pass property of the factor ( 1 − a z ) / ( z − a ) (1-az)/(z-a) ( 1 − a z ) / ( z − a ) yield ∑ k = 0 ∞ l i ( k ) l j ( k ) = δ i j \sum_{k=0}^{\infty}l_i(k)l_j(k)=\delta_{ij} ∑ k = 0 ∞ l i ( k ) l j ( k ) = δ ij [28 ] . We stack N N N basis functions where
L ( k ) : = [ l 1 ( k ) ⋯ l N ( k ) ] ⊤ L(k):=[l_1(k)\ \cdots\ l_N(k)]^\top L ( k ) := [ l 1 ( k ) ⋯ l N ( k ) ] ⊤
and let
β : = 1 − a 2 . \beta:=1-a^2. β := 1 − a 2 .
Then, L ( k ) L(k) L ( k ) evolves as follows [29 ] :
L ( k + 1 ) = Ω L ( k ) , (19) L(k+1)=\Omega L(k), \tag*{(19)} L ( k + 1 ) = Ω L ( k ) , (19)
where Ω \Omega Ω is given by
Ω : = [ a 0 ⋯ 0 β a ⋯ 0 ⋮ ⋱ ⋱ ⋮ ( − a ) N − 2 β ⋯ β a ] (20) \Omega:=\begin{bmatrix}
a & 0 & \cdots& 0\\
\beta& a & \cdots& 0\\
\vdots& \ddots& \ddots& \vdots\\
(-a)^{N-2}\beta& \cdots& \beta& a
\end{bmatrix} \tag*{(20)} Ω := a β ⋮ ( − a ) N − 2 β 0 a ⋱ ⋯ ⋯ ⋯ ⋱ β 0 0 ⋮ a (20)
and L ( 0 ) L(0) L ( 0 ) is given by
L ( 0 ) : = β [ 1 − a a 2 ⋯ ( − a ) N − 1 ] ⊤ . L(0):=\sqrt{\beta}\,[1\quad-a\quad a^2\quad\cdots\quad(-a)^{N-1}]^\top. L ( 0 ) := β [ 1 − a a 2 ⋯ ( − a ) N − 1 ] ⊤ .
To illustrate the Laguerre basis, Figure 1 shows the basis functions up to the order N = 5 N=5 N = 5 for the pole a = 0.5 a=0.5 a = 0.5 . As the figure illustrates, the Laguerre basis has the following two properties.
Figure 1. Example of discrete-time Laguerre basis functions with the pole a = 0.5 a=0.5 a = 0.5 .
Since each basis function decays exponentially in time, the basis represents the inputs in the first part of the prediction horizon finely and those in the latter part coarsely.
The peak of a basis function is delayed as its order increases.
The first property originates from the first-order low-pass factor 1 − a 2 / ( z − a ) \sqrt{1-a^2}/(z-a) 1 − a 2 / ( z − a ) in (17), which is common to all basis functions. This factor alone yields the first basis function l 1 ( k ) = β a k l_1(k)=\sqrt{\beta}\,a^k l 1 ( k ) = β a k , which decays exponentially with ratio a a a , and the higher-order basis functions inherit this decay. The second property originates from the all-pass factor ( 1 − a z ) / ( z − a ) (1-az)/(z-a) ( 1 − a z ) / ( z − a ) , which is multiplied once more for each increase in the order [32 ] . Since the all-pass factor does not change the magnitude response, it only adds phase lag. At low frequencies, this lag corresponds to a time delay of ( 1 + a ) / ( 1 − a ) (1+a)/(1-a) ( 1 + a ) / ( 1 − a ) steps. Hence each increase in the order shifts the peak of the basis function later in time. As a consequence of the second property, the low-order basis functions concentrate on the beginning of the prediction horizon, and a small number of low-order basis functions suffices to represent the inputs at the beginning of the prediction horizon.
Using the Laguerre basis introduced above, we expand the inputs in the basis and derive the linear relationship between the coefficients and the inputs. We focus on the r r r -th channel of v ( k ) v(k) v ( k ) , denoted by v r ( k ) v_r(k) v r ( k ) , and present its expansion:
v r ( k ) = ∑ i = 1 N s i r θ i r l i ( k ) , (21) v_r(k)=\sum_{i=1}^{N}s_{ir}\theta_{ir}l_i(k), \tag*{(21)} v r ( k ) = i = 1 ∑ N s i r θ i r l i ( k ) , (21)
where θ i r ∈ R \theta_{ir}\in\mathbb{R} θ i r ∈ R is the coefficient, and s i r ∈ { 0 , 1 } s_{ir}\in\{0,1\} s i r ∈ { 0 , 1 } is the indicator. If s i r = 1 s_{ir}=1 s i r = 1 , the i i i -th basis function is used for the expansion, and if s i r = 0 s_{ir}=0 s i r = 0 , it is omitted. Suppose that d d d basis functions are selected from N N N candidates l 1 ( k ) , … , l N ( k ) l_1(k),\ldots,l_N(k) l 1 ( k ) , … , l N ( k ) , i.e., it holds that
∑ i = 1 N s i r = d . \sum_{i=1}^{N}s_{ir}=d. i = 1 ∑ N s i r = d .
Let I r : = { i 1 r , … , i d r } \mathcal{I}_r:=\{i_{1r},\ldots,i_{dr}\} I r := { i 1 r , … , i d r } be the index set of the basis functions selected in the r r r -th channel. Furthermore, letting e i ∈ R N e_i\in\mathbb{R}^{N} e i ∈ R N be the i i i -th unit vector, we define
S r : = [ e i 1 r ⋯ e i d r ] ∈ { 0 , 1 } N × d . S_r:=[e_{i_{1r}}\ \cdots\ e_{i_{dr}}]\in\{0,1\}^{N\times d}. S r := [ e i 1 r ⋯ e i d r ] ∈ { 0 , 1 } N × d .
Then, we rewrite the expansion (21) in matrix form as
v r ( k ) = L ( k ) T S r S r T θ r , v_r(k)=L(k)^{\mathsf T}S_rS_r^{\mathsf T}\theta_r, v r ( k ) = L ( k ) T S r S r T θ r ,
where
θ r : = [ θ 1 r ⋯ θ N r ] T . \theta_r:=[\theta_{1r}\ \cdots\ \theta_{Nr}]^{\mathsf T}. θ r := [ θ 1 r ⋯ θ N r ] T .
Furthermore, letting
ϑ : = [ θ 1 T ⋯ θ m T ] T ∈ R m N , \vartheta:=[\theta_1^{\mathsf T}\ \cdots\ \theta_m^{\mathsf T}]^{\mathsf T}\in\mathbb{R}^{mN}, ϑ := [ θ 1 T ⋯ θ m T ] T ∈ R m N ,
S : = diag ( S 1 , … , S m ) ∈ { 0 , 1 } m N × m d , S:=\operatorname{diag}(S_1,\ldots,S_m)\in\{0,1\}^{mN\times md}, S := diag ( S 1 , … , S m ) ∈ { 0 , 1 } m N × m d ,
ϑ S : = S T ϑ ∈ R m d , \vartheta_S:=S^{\mathsf T}\vartheta\in\mathbb{R}^{md}, ϑ S := S T ϑ ∈ R m d ,
we have the expression of the sampled input v ( k ) v(k) v ( k ) as
v ( k ) = P S ( k ) ϑ S , (22) v(k)=P_S(k)\vartheta_S, \tag*{(22)} v ( k ) = P S ( k ) ϑ S , (22)
where P S ( k ) P_S(k) P S ( k ) is given by
P S ( k ) : = ( I m ⊗ L ( k ) T ) S ∈ R m × m d . (23) P_S(k):=(I_m\otimes L(k)^{\mathsf T})S\in\mathbb{R}^{m\times md}. \tag*{(23)} P S ( k ) := ( I m ⊗ L ( k ) T ) S ∈ R m × m d . (23)
For simplicity of notation, we present the expansion of the sampled input sequence V V V , given in (2), in vector form. We define the sampled input vector by
V : = vec ( V T ) . \mathcal{V}:=\operatorname{vec}(V^{\mathsf T}). V := vec ( V T ) .
Then, we have the expression
V = Q S ϑ S , \mathcal{V}=Q_S\vartheta_S, V = Q S ϑ S ,
where
Q S : = ( I m ⊗ Φ T ) S ∈ R m T × m d , (24) Q_S:=(I_m\otimes\Phi^{\mathsf T})S\in\mathbb{R}^{mT\times md}, \tag*{(24)} Q S := ( I m ⊗ Φ T ) S ∈ R m T × m d , (24)
Φ : = [ L ( 0 ) ⋯ L ( T − 1 ) ] . (25) \Phi:=[L(0)\ \cdots\ L(T-1)]. \tag*{(25)} Φ := [ L ( 0 ) ⋯ L ( T − 1 )] . (25)
In a similar manner to v ( k ) v(k) v ( k ) , we present the expansions of the mean input u ( k ) u(k) u ( k ) , the reference input u ~ ( k ) \widetilde{u}(k) u ( k ) , and the initial estimate input u ^ ( k ) \widehat{u}(k) u ( k ) as
u ( k ) = P S ( k ) ϖ S , (26) u(k)=P_S(k)\varpi_S, \tag*{(26)} u ( k ) = P S ( k ) ϖ S , (26)
u ~ ( k ) = P S ( k ) ϖ ~ S , (27) \widetilde{u}(k)=P_S(k)\widetilde{\varpi}_S, \tag*{(27)} u ( k ) = P S ( k ) ϖ S , (27)
u ^ ( k ) = P S ( k ) ϖ ^ S , (28) \widehat{u}(k)=P_S(k)\widehat{\varpi}_S, \tag*{(28)} u ( k ) = P S ( k ) ϖ S , (28)
where the coefficients ϖ S , ϖ ~ S , ϖ ^ S ∈ R m d \varpi_S,\widetilde{\varpi}_S,\widehat{\varpi}_S\in\mathbb{R}^{md} ϖ S , ϖ S , ϖ S ∈ R m d are called the mean coefficient, the reference coefficient, and the initial estimate coefficient, respectively.
We clarify the properties of Φ \Phi Φ , defined in (25), and discuss the relation between the sampled input vector V \mathcal{V} V and the selected coefficient ϑ S \vartheta_S ϑ S . To this end, we impose the following assumption regarding the prediction horizon T T T and the number of candidate basis functions N N N .
Assumption 3: T ≥ N T\geq N T ≥ N .
Under this assumption, the following lemma holds.
Lemma 4: Under Assumption 3, the following three statements hold.
The pair ( Ω , L ( 0 ) ) (\Omega,L(0)) ( Ω , L ( 0 )) is controllable.
rank ( Φ ) = N \operatorname{rank}(\Phi)=N rank ( Φ ) = N .
Φ Φ T ≻ 0 \Phi\Phi^{\mathsf T}\succ0 Φ Φ T ≻ 0 .
Proof: 1) We show that the controllability matrix
M Ω : = [ L ( 0 ) Ω L ( 0 ) ⋯ Ω N − 1 L ( 0 ) ] ∈ R N × N \mathcal{M}_{\Omega}:=[L(0)\ \Omega L(0)\ \cdots\ \Omega^{N-1}L(0)]\in\mathbb{R}^{N\times N} M Ω := [ L ( 0 ) Ω L ( 0 ) ⋯ Ω N − 1 L ( 0 )] ∈ R N × N
is invertible. Using the recursion (19) repeatedly, we have L ( k ) = Ω k L ( 0 ) L(k)=\Omega^kL(0) L ( k ) = Ω k L ( 0 ) . The matrix Ω \Omega Ω , defined in (20) , is decomposed as Ω = a I N + D \Omega=aI_N+D Ω = a I N + D with a strictly lower triangular matrix D D D . The ( i , j ) (i,j) ( i , j ) entry of the matrix D D D is D i j = β ( − a ) i − j − 1 D_{ij}=\beta(-a)^{i-j-1} D ij = β ( − a ) i − j − 1 for i > j i>j i > j . In particular, D i , i − 1 = β > 0 D_{i,i-1}=\beta>0 D i , i − 1 = β > 0 for i = j + 1 i=j+1 i = j + 1 . Since the matrices a I N aI_N a I N and D D D commute, the binomial theorem gives
L ( k ) = Ω k L ( 0 ) = ∑ i = 0 k ( k i ) a k − i D i L ( 0 ) . L(k)=\Omega^kL(0)=\sum_{i=0}^{k}\binom{k}{i}a^{k-i}D^iL(0). L ( k ) = Ω k L ( 0 ) = i = 0 ∑ k ( i k ) a k − i D i L ( 0 ) .
Therefore, we have the expression
M Ω = M D A , \mathcal{M}_{\Omega}=\mathcal{M}_{D}\mathcal{A}, M Ω = M D A ,
where the matrices M D ∈ R N × N \mathcal{M}_{D}\in\mathbb{R}^{N\times N} M D ∈ R N × N and A ∈ R N × N \mathcal{A}\in\mathbb{R}^{N\times N} A ∈ R N × N are given by
M D : = [ L ( 0 ) D L ( 0 ) ⋯ D N − 1 L ( 0 ) ] , \mathcal{M}_{D}:=[L(0)\quad DL(0)\quad\cdots\quad D^{N-1}L(0)], M D := [ L ( 0 ) D L ( 0 ) ⋯ D N − 1 L ( 0 )] ,
A : = [ 1 a ⋯ a N − 1 0 1 ⋯ ( N − 1 1 ) a N − 2 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ 1 ] , \mathcal{A}:=
\begin{bmatrix}
1&a&\cdots&a^{N-1}\\
0&1&\cdots&\binom{N-1}{1}a^{N-2}\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&1
\end{bmatrix}, A := 1 0 ⋮ 0 a 1 ⋮ 0 ⋯ ⋯ ⋱ ⋯ a N − 1 ( 1 N − 1 ) a N − 2 ⋮ 1 ,
respectively. Since the matrix A \mathcal{A} A is upper triangular and its diagonal entries are all 1 1 1 , it is invertible. Hence the controllability matrix M Ω \mathcal{M}_{\Omega} M Ω is invertible if and only if the matrix M D \mathcal{M}_{D} M D is invertible. Since the matrix D k D^k D k is strictly lower triangular, the first k k k entries of the vector D k L ( 0 ) D^kL(0) D k L ( 0 ) are zero, and
D k L ( 0 ) = [ 0 ⋯ 0 β k + 1 2 ∗ ⋯ ∗ ] ⊤ . D^kL(0)=[0\ \cdots\ 0\ \beta^{k+\frac{1}{2}}\ *\ \cdots\ *]^{\top}. D k L ( 0 ) = [ 0 ⋯ 0 β k + 2 1 ∗ ⋯ ∗ ] ⊤ .
Therefore the matrix M D \mathcal{M}_{D} M D is lower triangular, and its diagonal entries β k + 1 2 \beta^{k+\frac{1}{2}} β k + 2 1 , k ∈ { 0 , … , N − 1 } k\in\{0,\ldots,N-1\} k ∈ { 0 , … , N − 1 } , are positive since β > 0 \beta>0 β > 0 for any pole a ∈ [ 0 , 1 ) a\in[0,1) a ∈ [ 0 , 1 ) . Hence the matrix M D \mathcal{M}_{D} M D is invertible. Consequently, the pair ( Ω , L ( 0 ) ) (\Omega,L(0)) ( Ω , L ( 0 )) is controllable.
From Assumption 3, the first N N N columns of Φ = [ L ( 0 ) ⋯ L ( T − 1 ) ] \Phi=[L(0)\ \cdots\ L(T-1)] Φ = [ L ( 0 ) ⋯ L ( T − 1 )] , defined in (25) , form the controllability matrix M Ω \mathcal{M}_{\Omega} M Ω . Since the controllability matrix M Ω \mathcal{M}_{\Omega} M Ω is invertible as shown in 1), rank ( Φ ) ≥ N \operatorname{rank}(\Phi)\ge N rank ( Φ ) ≥ N . Thus, rank ( Φ ) = N \operatorname{rank}(\Phi)=N rank ( Φ ) = N .
It follows from 2) that Φ Φ ⊤ ≻ 0 \Phi\Phi^{\top}\succ0 Φ Φ ⊤ ≻ 0 holds. ■
Using Lemma 4, we derive the following lemma.
Lemma 5: Under Assumption 3, Q S Q_S Q S , defined in (24) , is of full column rank.
Proof: By 2) of Lemma 4, I m ⊗ Φ ⊤ I_m\otimes\Phi^{\top} I m ⊗ Φ ⊤ is of full column rank. Since the columns of the selection matrix S S S are distinct unit vectors, Q S = ( I m ⊗ Φ ⊤ ) S Q_S=(I_m\otimes\Phi^{\top})S Q S = ( I m ⊗ Φ ⊤ ) S is also of full column rank. ■
As stated in Lemma 5, Q S Q_S Q S is of full column rank, and hence the selected coefficient ϑ S \vartheta_S ϑ S and the sampled input vector V V V are in one-to-one correspondence. The number of selected basis functions typically satisfies d < T d<T d < T . Then, the sampled input vector V V V takes values in the m d md m d -dimensional subspace Im ( Q S ) \operatorname{Im}(Q_S) Im ( Q S ) of R m T \mathbb{R}^{mT} R m T and therefore has no probability density on R m T \mathbb{R}^{mT} R m T . Hence the derivation of MPPI in Section II, which assumes that the sampled input sequence has a probability density on R m T \mathbb{R}^{mT} R m T , is not applicable to the sampled input sequence expanded in the Laguerre basis. We therefore search for a solution to the control problem indirectly in the coefficient space of ϑ S \vartheta_S ϑ S , rather than directly in the input space of V V V .
Optimal control problem in the coefficient space
Recall that MPPI solves Problem 1 by optimizing the mean U U U of the distribution of the sampled input sequence V V V . Instead, in this subsection, we optimize the mean ϖ S \varpi_S ϖ S of the distribution of the selected coefficient ϑ S \vartheta_S ϑ S . To this end, we first formulate a counterpart of Problem 1 in the coefficient space.
Let Σ S ∈ R m d × m d \Sigma_S\in\mathbb{R}^{md\times md} Σ S ∈ R m d × m d with Σ S ≻ 0 \Sigma_S\succ0 Σ S ≻ 0 be the covariance matrix of the selected coefficient. Analogously to the control distribution Q U \mathbb{Q}_U Q U , the reference distribution Q ~ \widetilde{\mathbb{Q}} Q , and the initial estimate distribution Q ^ \widehat{\mathbb{Q}} Q , introduced in Section II, we define the corresponding distributions in the coefficient space as
Q ϖ S : = N ( ϖ S , Σ S ) , \mathbb{Q}_{\varpi_S}:=\mathcal{N}(\varpi_S,\Sigma_S), Q ϖ S := N ( ϖ S , Σ S ) ,
Q ~ S : = N ( ϖ ~ S , Σ S ) , \widetilde{\mathbb{Q}}_S:=\mathcal{N}(\widetilde{\varpi}_S,\Sigma_S), Q S := N ( ϖ S , Σ S ) ,
Q ^ S : = N ( ϖ ^ S , Σ S ) , \widehat{\mathbb{Q}}_S:=\mathcal{N}(\widehat{\varpi}_S,\Sigma_S), Q S := N ( ϖ S , Σ S ) ,
where the mean coefficient ϖ S \varpi_S ϖ S , the reference coefficient ϖ ~ S \widetilde{\varpi}_S ϖ S , and the initial estimate coefficient ϖ ^ S \widehat{\varpi}_S ϖ S are those in (26) –(28) . In the coefficient space, we call Q ϖ S \mathbb{Q}_{\varpi_S} Q ϖ S , Q ~ S \widetilde{\mathbb{Q}}_S Q S , and Q ^ S \widehat{\mathbb{Q}}_S Q S the control distribution, the reference distribution, and the initial estimate distribution, respectively. Since Σ S \Sigma_S Σ S is positive definite, these distributions have probability densities on R m d \mathbb{R}^{md} R m d . In addition, let the function S ϑ S : R m d → R \mathcal{S}_{\vartheta_S}:\mathbb{R}^{md}\to\mathbb{R} S ϑ S : R m d → R be given by
S ϑ S ( ϑ S ) : = S ( V ( ϑ S ) ) , (29) \mathcal{S}_{\vartheta_S}(\vartheta_S):=S(V(\vartheta_S)), \tag*{(29)} S ϑ S ( ϑ S ) := S ( V ( ϑ S )) , (29)
which returns the cost of the sampled input sequence V V V generated from the selected coefficient ϑ S \vartheta_S ϑ S by (22) . Furthermore, we define the coefficient cost b S ( ϖ S ) b_S(\varpi_S) b S ( ϖ S ) instead of the input cost b k ( u ( k ) ) b_k(u(k)) b k ( u ( k )) , given in (8) , as
b S ( ϖ S ) : = λ 2 ∥ ϖ S − ϖ ~ S ∥ Σ S − 1 2 . (30) b_S(\varpi_S):=\frac{\lambda}{2}\lVert\varpi_S-\widetilde{\varpi}_S\rVert^2_{\Sigma_S^{-1}}. \tag*{(30)} b S ( ϖ S ) := 2 λ ∥ ϖ S − ϖ S ∥ Σ S − 1 2 . (30)
With this preparation, we formulate the stochastic optimal control problem in the coefficient space as follows.
Problem 4 (Coefficient-Space Optimal Control):
min ϖ S ∈ R m d E Q ϖ S [ ϕ ( x ( T ) ) + ∑ k = 0 T − 1 c k ( x ( k ) ) ] + b S ( ϖ S ) . (31) \min_{\varpi_S\in\mathbb{R}^{md}}\ \mathbb{E}_{\mathbb{Q}_{\varpi_S}}\left[\phi(x(T))+\sum_{k=0}^{T-1}c_k(x(k))\right]+b_S(\varpi_S). \tag*{(31)} ϖ S ∈ R m d min E Q ϖ S [ ϕ ( x ( T )) + k = 0 ∑ T − 1 c k ( x ( k )) ] + b S ( ϖ S ) . (31)
The first term of the cost function is the expected state cost of the sampled input sequence V V V generated by (22) from the selected coefficient ϑ S \vartheta_S ϑ S that follows the control distribution Q ϖ S \mathbb{Q}_{\varpi_S} Q ϖ S . The second term penalizes the discrepancy between the mean coefficient ϖ S \varpi_S ϖ S and the reference coefficient ϖ ~ S \widetilde{\varpi}_S ϖ S .
MPPI in the coefficient space
We solve Problem 4 approximately by a sampling-based approach. In a similar manner to the derivation of MPPI, we derive the following key theorem on the approximation of the solution to Problem 4. For a distribution Q S \mathbb{Q}_{\mathcal{S}} Q S with a probability density on R m d \mathbb{R}^{md} R m d , let the cost function in the coefficient space be
J ( Q S ) : = E Q S [ S ϑ S ( ϑ S ) ] + λ D K L ( Q S ∥ Q ~ S ) . J(\mathbb{Q}_{\mathcal{S}}) := \mathbb{E}_{\mathbb{Q}_{\mathcal{S}}}[S_{\vartheta_{\mathcal{S}}}(\vartheta_{\mathcal{S}})] + \lambda D_{\mathrm{KL}}(\mathbb{Q}_{\mathcal{S}}\|\widetilde{\mathbb{Q}}_{\mathcal{S}}). J ( Q S ) := E Q S [ S ϑ S ( ϑ S )] + λ D KL ( Q S ∥ Q S ) .
Then, consider the problem of min Q S J ( Q S ) \min_{\mathbb{Q}_{\mathcal{S}}} J(\mathbb{Q}_{\mathcal{S}}) min Q S J ( Q S ) , which is a relaxation of Problem 4. For this relaxed problem, we have the following theorem.
Theorem 2: The following four statements hold.
The cost function J ( Q ϖ S ) J(\mathbb{Q}_{\varpi_{\mathcal{S}}}) J ( Q ϖ S ) equals the objective function of (31).
The unique solution to the relaxed problem min Q S J ( Q S ) \min_{\mathbb{Q}_{\mathcal{S}}} J(\mathbb{Q}_{\mathcal{S}}) min Q S J ( Q S ) is given by the optimal distribution Q S ∗ \mathbb{Q}_{\mathcal{S}}^* Q S ∗ with the probability density function
q S ∗ ( ϑ S ) : = 1 η S exp ( − S ϑ S ( ϑ S ) λ ) q ~ S ( ϑ S ) , (32) q_{\mathcal{S}}^*(\vartheta_{\mathcal{S}}) := \frac{1}{\eta_{\mathcal{S}}}\exp\left(-\frac{S_{\vartheta_{\mathcal{S}}}(\vartheta_{\mathcal{S}})}{\lambda}\right)\widetilde{q}_{\mathcal{S}}(\vartheta_{\mathcal{S}}), \tag*{(32)} q S ∗ ( ϑ S ) := η S 1 exp ( − λ S ϑ S ( ϑ S ) ) q S ( ϑ S ) , (32) where η S \eta_{\mathcal{S}} η S is the normalization constant and is given by
η S : = E Q ~ S [ exp ( − S ϑ S ( ϑ S ) / λ ) ] . \eta_{\mathcal{S}} := \mathbb{E}_{\widetilde{\mathbb{Q}}_{\mathcal{S}}}\left[\exp\left(-S_{\vartheta_{\mathcal{S}}}(\vartheta_{\mathcal{S}})/\lambda\right)\right]. η S := E Q S [ exp ( − S ϑ S ( ϑ S ) / λ ) ] . In addition, it holds that
J ( Q S ∗ ) = − λ ln η S = : F S , J(\mathbb{Q}_{\mathcal{S}}^*)=-\lambda\ln\eta_{\mathcal{S}}=:F_{\mathcal{S}}, J ( Q S ∗ ) = − λ ln η S =: F S , which equals the free energy in the coefficient space.
The solution to the KL divergence minimization problem min ϖ S D K L ( Q S ∗ ∥ Q ϖ S ) \min_{\varpi_{\mathcal{S}}}D_{\mathrm{KL}}(\mathbb{Q}_{\mathcal{S}}^*\|\mathbb{Q}_{\varpi_{\mathcal{S}}}) min ϖ S D KL ( Q S ∗ ∥ Q ϖ S ) is given in closed form by
ϖ S ∗ = E Q S ∗ [ ϑ S ] . \varpi_{\mathcal{S}}^*=\mathbb{E}_{\mathbb{Q}_{\mathcal{S}}^*}[\vartheta_{\mathcal{S}}]. ϖ S ∗ = E Q S ∗ [ ϑ S ] . For the initial estimate distribution Q ^ S \widehat{\mathbb{Q}}_{\mathcal{S}} Q S , the optimal coefficient ϖ S ∗ \varpi_{\mathcal{S}}^* ϖ S ∗ is expressed with the weight w S ( ϑ S ) w_{\mathcal{S}}(\vartheta_{\mathcal{S}}) w S ( ϑ S ) as
ϖ S ∗ = E Q ^ S [ w S ϑ S ] E Q ^ S [ w S ] , (33) \varpi_{\mathcal{S}}^*=\frac{\mathbb{E}_{\widehat{\mathbb{Q}}_{\mathcal{S}}}[w_{\mathcal{S}}\vartheta_{\mathcal{S}}]}{\mathbb{E}_{\widehat{\mathbb{Q}}_{\mathcal{S}}}[w_{\mathcal{S}}]}, \tag*{(33)} ϖ S ∗ = E Q S [ w S ] E Q S [ w S ϑ S ] , (33) w S ( ϑ S ) : = exp ( − S ϑ S ( ϑ S ) λ − ( ϖ ^ S − ϖ ~ S ) T Σ S − 1 ϑ S ) . (34) w_{\mathcal{S}}(\vartheta_{\mathcal{S}}):=\exp\left(-\frac{S_{\vartheta_{\mathcal{S}}}(\vartheta_{\mathcal{S}})}{\lambda}-(\widehat{\varpi}_{\mathcal{S}}-\widetilde{\varpi}_{\mathcal{S}})^{\mathsf{T}}\Sigma_{\mathcal{S}}^{-1}\vartheta_{\mathcal{S}}\right). \tag*{(34)} w S ( ϑ S ) := exp ( − λ S ϑ S ( ϑ S ) − ( ϖ S − ϖ S ) T Σ S − 1 ϑ S ) . (34)
Proof: Each statement follows from the derivation of its counterpart in Section II with the sampled input sequence V V V , the mean input sequence U U U , and the integration domain R m × T \mathbb{R}^{m\times T} R m × T replaced by the selected coefficient ϑ S \vartheta_{\mathcal{S}} ϑ S , the mean coefficient ϖ S \varpi_{\mathcal{S}} ϖ S , and R m d \mathbb{R}^{md} R m d , respectively. The derivations in Section II use only two properties of the distributions. One is that the distributions have probability densities, and the other is that the control distribution Q U \mathbb{Q}_{U} Q U , the reference distribution Q ~ \widetilde{\mathbb{Q}} Q , and the initial estimate distribution Q ^ \widehat{\mathbb{Q}} Q are Gaussian with a common covariance matrix. Both properties hold in the coefficient space, since the covariance matrix Σ S \Sigma_{\mathcal{S}} Σ S is positive definite and is shared by the distributions Q ϖ S \mathbb{Q}_{\varpi_{\mathcal{S}}} Q ϖ S , Q ~ S \widetilde{\mathbb{Q}}_{\mathcal{S}} Q S , and Q ^ S \widehat{\mathbb{Q}}_{\mathcal{S}} Q S . The only difference in the computation is that the sum ∑ k = 0 T − 1 ( ⋅ ) T Σ − 1 ( ⋅ ) \sum_{k=0}^{T-1}(\cdot)^{\mathsf{T}}\Sigma^{-1}(\cdot) ∑ k = 0 T − 1 ( ⋅ ) T Σ − 1 ( ⋅ ) of quadratic forms over time becomes the single quadratic form ( ⋅ ) T Σ S − 1 ( ⋅ ) (\cdot)^{\mathsf{T}}\Sigma_{\mathcal{S}}^{-1}(\cdot) ( ⋅ ) T Σ S − 1 ( ⋅ ) .
Statement 1) follows from the proof of Lemma 2 with Assumption 2 replaced by the definition (30). The derivation gives λ D K L ( Q ϖ S ∥ Q ~ S ) = λ 2 ∥ ϖ S − ϖ ~ S ∥ Σ S − 1 2 \lambda D_{\mathrm{KL}}(\mathbb{Q}_{\varpi_{\mathcal{S}}}\|\widetilde{\mathbb{Q}}_{\mathcal{S}})=\frac{\lambda}{2}\|\varpi_{\mathcal{S}}-\widetilde{\varpi}_{\mathcal{S}}\|_{\Sigma_{\mathcal{S}}^{-1}}^2 λ D KL ( Q ϖ S ∥ Q S ) = 2 λ ∥ ϖ S − ϖ S ∥ Σ S − 1 2 , which equals the coefficient cost b S ( ϖ S ) b_{\mathcal{S}}(\varpi_{\mathcal{S}}) b S ( ϖ S ) .
Statement 2) follows from the proof of Lemma 3.
Statement 3) follows since the KL divergence D K L ( Q S ∗ ∥ Q ϖ S ) D_{\mathrm{KL}}(\mathbb{Q}_{\mathcal{S}}^*\|\mathbb{Q}_{\varpi_{\mathcal{S}}}) D KL ( Q S ∗ ∥ Q ϖ S ) equals 1 2 E Q S ∗ [ ∥ ϑ S − ϖ S ∥ Σ S − 1 2 ] \frac{1}{2}\mathbb{E}_{\mathbb{Q}_{\mathcal{S}}^*}[\|\vartheta_{\mathcal{S}}-\varpi_{\mathcal{S}}\|_{\Sigma_{\mathcal{S}}^{-1}}^2] 2 1 E Q S ∗ [ ∥ ϑ S − ϖ S ∥ Σ S − 1 2 ] up to a constant independent of ϖ S \varpi_{\mathcal{S}} ϖ S , and its minimizer is the mean E Q S ∗ [ ϑ S ] \mathbb{E}_{\mathbb{Q}_{\mathcal{S}}^*}[\vartheta_{\mathcal{S}}] E Q S ∗ [ ϑ S ] of the optimal distribution.
Statement 4) follows from the proof of Theorem 1, which gives the density ratio
ln q ~ S ( ϑ S ) q ^ S ( ϑ S ) = − ( ϖ ^ S − ϖ ~ S ) T Σ S − 1 ϑ S + c o n s t . , \ln\frac{\widetilde{q}_{\mathcal{S}}(\vartheta_{\mathcal{S}})}{\widehat{q}_{\mathcal{S}}(\vartheta_{\mathcal{S}})}
=-(\widehat{\varpi}_{\mathcal{S}}-\widetilde{\varpi}_{\mathcal{S}})^{\mathsf{T}}\Sigma_{\mathcal{S}}^{-1}\vartheta_{\mathcal{S}}+\mathrm{const.}, ln q S ( ϑ S ) q S ( ϑ S ) = − ( ϖ S − ϖ S ) T Σ S − 1 ϑ S + const. ,
where the constant term does not depend on ϑ S \vartheta_{\mathcal{S}} ϑ S . Therefore, (33) and (34) follow. ■
Statement 4) of Theorem 2 enables us to develop a new MPPI scheme that samples in the coefficient space. Before presenting its details, we compare it with the conventional MPPI scheme given in Algorithm 1 as follows.
a) Decision variables: Problem 1 optimizes the mean input sequence U U U directly, whereas Problem 4 optimizes the mean coefficient ϖ S \varpi_{\mathcal{S}} ϖ S , which determines U U U through (26). This parameterization restricts U U U to the m d md m d -dimensional subspace Im ( S ) \operatorname{Im}(\mathcal{S}) Im ( S ) .
b) Random variables: The random variable of MPPI is the sampled input sequence V ∈ R m × T V\in\mathbb{R}^{m\times T} V ∈ R m × T , whereas that of the coefficient-space formulation is the selected coefficient ϑ S ∈ R m d \vartheta_{\mathcal{S}}\in\mathbb{R}^{md} ϑ S ∈ R m d . Both formulations evaluate the state cost with the same function S S S , defined in (4), and the coefficient-space formulation evaluates it through V V V generated from ϑ S \vartheta_{\mathcal{S}} ϑ S .
c) Input costs: MPPI uses the input cost (8), whereas the coefficient-space formulation uses the coefficient cost (30).
d) Covariance: MPPI assigns the covariance matrix Σ v \Sigma_v Σ v to the sampled input v ( k ) v(k) v ( k ) independently at each time, whereas the covariance matrix Σ S \Sigma_{\mathcal{S}} Σ S of the selected coefficient is an arbitrary positive definite matrix and may include correlations across basis functions and channels.
Laguerre-MPPI algorithm: We now define Laguerre-MPPI as the sampling-based control method that approximately solves Problem 4 based on Theorem 2. The detailed procedure is summarized in Algorithm 2. Figure 2 illustrates the difference in the generation of the sampled input sequence between Laguerre-MPPI and conventional MPPI. In conventional MPPI, the sampled input v ( k ) v(k) v ( k ) at each time independently follows N ( u ^ ( k ) , Σ v ) \mathcal{N}(\widehat{u}(k),\Sigma_v) N ( u ( k ) , Σ v ) . Hence the sampled input sequence fluctuates from one time step to the next and is not smooth. In Laguerre-MPPI, the selected coefficient is sampled instead, and each sampled input sequence is a linear combination of the selected basis functions l i ( k ) l_i(k) l i ( k ) , defined in (18). Since each basis function has low-pass characteristics for any pole a > 0 a>0 a > 0 , both the sampled input sequence and the mean input sequence are smooth in time. The dimension of the selected coefficient is m d md m d , which does not depend on the prediction horizon T T T .
Figure 2. Comparison between MPPI and Laguerre-MPPI.
Remark 1: After applying the first input, Laguerre-MPPI shifts the computed input sequence by one step, projects it onto the subspace spanned by the selected basis functions by
Algorithm 2 Laguerre-MPPI
Require: M M M , T T T , λ \lambda λ , a a a , S S S , Σ S \Sigma_S Σ S , ϖ ~ S \widetilde{\varpi}_S ϖ S , ϖ ^ S \widehat{\varpi}_S ϖ S
for k = 0 , 1 , 2 , … k = 0, 1, 2, \ldots k = 0 , 1 , 2 , … do
Generate { ϑ S i } i = 1 M \{\vartheta_S^i\}_{i=1}^{M} { ϑ S i } i = 1 M from Q ^ S = N ( ϖ ^ S , Σ S ) \widehat{Q}_S = \mathcal{N}(\widehat{\varpi}_S, \Sigma_S) Q S = N ( ϖ S , Σ S )
for i = 1 , … , M i = 1, \ldots, M i = 1 , … , M do
Convert ϑ S i \vartheta_S^i ϑ S i into V i V^i V i by (22)
Apply V i V^i V i to (1) and compute S ϑ S ( ϑ S i ) S_{\vartheta_S}(\vartheta_S^i) S ϑ S ( ϑ S i )
Compute w S ( ϑ S i ) w_S(\vartheta_S^i) w S ( ϑ S i ) by (34)
end for
ϖ ~ S ← ∑ i = 1 M w S ( ϑ S i ) ϑ S i ∑ i = 1 M w S ( ϑ S i ) \widetilde{\varpi}_S \leftarrow\dfrac{\sum_{i=1}^{M} w_S(\vartheta_S^i)\vartheta_S^i}{\sum_{i=1}^{M} w_S(\vartheta_S^i)} ϖ S ← ∑ i = 1 M w S ( ϑ S i ) ∑ i = 1 M w S ( ϑ S i ) ϑ S i
Apply u i ( 0 ) = P S ( 0 ) ϖ ~ S u^i(0) = P_S(0)\widetilde{\varpi}_S u i ( 0 ) = P S ( 0 ) ϖ S to the system
Update ϖ ^ S \widehat{\varpi}_S ϖ S
end for
least squares, and uses the resulting coefficient as the initial estimate coefficient ϖ ^ S \widehat{\varpi}_S ϖ S at the next time. In conventional MPPI, the computed input sequence is shifted by one step, the last input is set to zero, and the result is used as the mean U ^ \widehat{U} U of the initial estimate distribution at the next time step.
Table I summarizes the correspondence between conventional MPPI and Laguerre-MPPI in terms of the random variables, the search dimensions, and other quantities.
Table I. Correspondence between MPPI and Laguerre-MPPI
For clarity, Table II summarizes the roles of the distributions in Laguerre-MPPI. The distributions in MPPI play the same roles.
Table II. Distributions in Laguerre-MPPI
Consistency with MPPI
Laguerre-MPPI restricts the input of MPPI to an m d md m d -dimensional subspace. When all basis functions are used with N = T N = T N = T , that is, when the selection matrix is S = I m T S = I_{mT} S = I m T , this subspace coincides with the whole input space R m T \mathbb{R}^{mT} R m T . Even in this case, Laguerre-MPPI does not reduce to MPPI for an arbitrary covariance matrix Σ S \Sigma_S Σ S of the selected coefficient, since Σ S \Sigma_S Σ S determines the following three quantities, which differ from those of MPPI in general.
Sampled input sequence: The covariance matrix of the sampled input sequence V V V generated from the selected coefficient by (22) is determined by Σ S \Sigma_S Σ S . Hence the sampled input sequence V V V does not follow the initial estimate distribution Q ^ \widehat{Q} Q of MPPI in general.
Input costs: The coefficient cost b S ( ϖ S ) b_S(\varpi_S) b S ( ϖ S ) , defined in (30) , differs from the input cost b k ( u ( k ) ) b_k(u(k)) b k ( u ( k )) of MPPI, defined in (8) .
Weights: The weight w S w_S w S in (34) assigned to each sampled input sequence V V V differs from the weight w w w in (16) of MPPI.
For Laguerre-MPPI to reduce to MPPI, the covariance matrix Σ S \Sigma_S Σ S must satisfy a specific condition. We consider the following condition on the covariance matrix Σ S \Sigma_S Σ S :
Σ S − 1 = ∑ k = 0 T − 1 P S ( k ) T Σ v − 1 P S ( k ) . (35) \Sigma_S^{-1} = \sum_{k=0}^{T-1} P_S(k)^\mathsf{T}\Sigma_v^{-1}P_S(k). \tag*{(35)} Σ S − 1 = k = 0 ∑ T − 1 P S ( k ) T Σ v − 1 P S ( k ) . (35)
The following theorem shows the consistency of Laguerre-MPPI with MPPI.
Theorem 3: Let N = T N = T N = T and S = I m T S = I_{mT} S = I m T , and let the covariance matrix Σ S \Sigma_S Σ S satisfy (35) . Then, for any pole a ∈ [ 0 , 1 ) a \in[0,1) a ∈ [ 0 , 1 ) , the following two statements hold.
Let the selected coefficient ϑ S \vartheta_S ϑ S be sampled from Q ^ S = N ( ϖ ^ S , Σ S ) \widehat{Q}_S = \mathcal{N}(\widehat{\varpi}_S,\Sigma_S) Q S = N ( ϖ S , Σ S ) . Then, the sampled input sequence V V V generated from ϑ S \vartheta_S ϑ S by (22) follows Q ^ = N ( U ^ , Σ v ) \widehat{Q} = \mathcal{N}(\widehat{U},\Sigma_v) Q = N ( U , Σ v ) .
The input u i ( 0 ) = P S ( 0 ) ϖ ~ S u^i(0) = P_S(0)\widetilde{\varpi}_S u i ( 0 ) = P S ( 0 ) ϖ S generated by Algorithm 2 has the same distribution as the input u i ( 0 ) u^i(0) u i ( 0 ) generated by Algorithm 1.
To prove Theorem 3, we first present Lemmas 6 and 7.
Lemma 6: Under Assumption 3, the following two statements hold.
For vectors α , γ ∈ R m d \alpha,\gamma\in\mathbb{R}^{md} α , γ ∈ R m d , let
ξ ( k ) : = P S ( k ) α , (36) \xi(k):=P_{\mathcal{S}}(k)\alpha, \tag*{(36)} ξ ( k ) := P S ( k ) α , (36) ζ ( k ) : = P S ( k ) γ . (37) \zeta(k):=P_{\mathcal{S}}(k)\gamma. \tag*{(37)} ζ ( k ) := P S ( k ) γ . (37) Then, it holds that
α ⊤ [ ∑ k = 0 T − 1 P S ( k ) ⊤ Σ v − 1 P S ( k ) ] γ = ∑ k = 0 T − 1 ξ ( k ) ⊤ Σ v − 1 ζ ( k ) . (38) \alpha^{\top}\left[\sum_{k=0}^{T-1}P_{\mathcal{S}}(k)^{\top}\Sigma_v^{-1}P_{\mathcal{S}}(k)\right]\gamma=\sum_{k=0}^{T-1}\xi(k)^{\top}\Sigma_v^{-1}\zeta(k). \tag*{(38)} α ⊤ [ k = 0 ∑ T − 1 P S ( k ) ⊤ Σ v − 1 P S ( k ) ] γ = k = 0 ∑ T − 1 ξ ( k ) ⊤ Σ v − 1 ζ ( k ) . (38) The covariance matrix Σ S \Sigma_{\mathcal{S}} Σ S satisfying (35) is positive definite.
Proof. 1) By substituting (36) and (37) into the right-hand side of (38), we see that (38) holds.
Letting γ = α \gamma=\alpha γ = α in (38), we have
α ⊤ [ ∑ k = 0 T − 1 P S ( k ) ⊤ Σ v − 1 P S ( k ) ] α = ∑ k = 0 T − 1 ξ ( k ) ⊤ Σ v − 1 ξ ( k ) . \alpha^{\top}\left[\sum_{k=0}^{T-1}P_{\mathcal{S}}(k)^{\top}\Sigma_v^{-1}P_{\mathcal{S}}(k)\right]\alpha=\sum_{k=0}^{T-1}\xi(k)^{\top}\Sigma_v^{-1}\xi(k). α ⊤ [ k = 0 ∑ T − 1 P S ( k ) ⊤ Σ v − 1 P S ( k ) ] α = k = 0 ∑ T − 1 ξ ( k ) ⊤ Σ v − 1 ξ ( k ) .
This quadratic form is nonnegative and equals zero only if ξ ( k ) = P S ( k ) α = 0 \xi(k)=P_{\mathcal{S}}(k)\alpha=0 ξ ( k ) = P S ( k ) α = 0 for all k k k , i.e., Q S α = 0 Q_{\mathcal{S}}\alpha=0 Q S α = 0 . By Lemma 5, Q S Q_{\mathcal{S}} Q S is of full column rank, and hence this quadratic form is positive definite. This implies that Σ S − 1 \Sigma_{\mathcal{S}}^{-1} Σ S − 1 , defined in (35), is positive definite and completes the proof. ■
Statement 2) of Lemma 6 guarantees that the Gaussian distribution with the covariance matrix Σ S \Sigma_{\mathcal{S}} Σ S satisfying (35) is well defined, and hence samples are drawn from it.
Lemma 7: Suppose that Assumptions 1, 2, and 3 hold and that the covariance matrix Σ S \Sigma_{\mathcal{S}} Σ S satisfies (35). Then, the following three statements hold.
For any mean coefficient ϖ S \varpi_{\mathcal{S}} ϖ S and reference coefficient ϖ ~ S \tilde{\varpi}_{\mathcal{S}} ϖ ~ S , it holds that
b S ( ϖ S ) = ∑ k = 0 T − 1 b k ( u ( k ) ) . (39) b_{\mathcal{S}}(\varpi_{\mathcal{S}})=\sum_{k=0}^{T-1}b_k(u(k)). \tag*{(39)} b S ( ϖ S ) = k = 0 ∑ T − 1 b k ( u ( k )) . (39) The sampled input sequence V V V , generated by (22), satisfies
( ϖ ^ S − ϖ ~ S ) ⊤ Σ S − 1 ϑ S = ∑ k = 0 T − 1 ( u ^ ( k ) − u ~ ( k ) ) ⊤ Σ v − 1 v ( k ) . (40) (\hat{\varpi}_{\mathcal{S}}-\tilde{\varpi}_{\mathcal{S}})^{\top}\Sigma_{\mathcal{S}}^{-1}\vartheta_{\mathcal{S}}=\sum_{k=0}^{T-1}(\hat{u}(k)-\tilde{u}(k))^{\top}\Sigma_v^{-1}v(k). \tag*{(40)} ( ϖ ^ S − ϖ ~ S ) ⊤ Σ S − 1 ϑ S = k = 0 ∑ T − 1 ( u ^ ( k ) − u ~ ( k ) ) ⊤ Σ v − 1 v ( k ) . (40) When N = T N=T N = T and S = I m T \mathcal{S}=I_{mT} S = I m T , any mean input sequence U U U , reference input sequence U ~ \tilde{U} U ~ , and initial estimate input sequence U ^ \hat{U} U ^ are expressed in the form of (26)–(28).
Proof. 1) Substituting (26) and (27) into (8), we see that the right-hand side of (39) equals λ 2 ∑ k = 0 T − 1 ∥ P S ( k ) ( ϖ S − ϖ ~ S ) ∥ Σ v − 1 2 \frac{\lambda}{2}\sum_{k=0}^{T-1}\|P_{\mathcal{S}}(k)(\varpi_{\mathcal{S}}-\tilde{\varpi}_{\mathcal{S}})\|_{\Sigma_v^{-1}}^2 2 λ ∑ k = 0 T − 1 ∥ P S ( k ) ( ϖ S − ϖ ~ S ) ∥ Σ v − 1 2 . When the covariance matrix Σ S \Sigma_{\mathcal{S}} Σ S satisfies (35), applying 1) of Lemma 6 yields (39).
We apply 1) of Lemma 6 with α = ϖ ^ S − ϖ ~ S \alpha=\hat{\varpi}_{\mathcal{S}}-\tilde{\varpi}_{\mathcal{S}} α = ϖ ^ S − ϖ ~ S and γ = ϑ S \gamma=\vartheta_{\mathcal{S}} γ = ϑ S . Using the expansions (27) and (28), we see that ξ ( k ) \xi(k) ξ ( k ) , defined in (36), equals u ^ ( k ) − u ~ ( k ) \hat{u}(k)-\tilde{u}(k) u ^ ( k ) − u ~ ( k ) . Similarly, the expansion (22) shows that ζ ( k ) \zeta(k) ζ ( k ) , defined in (37), equals v ( k ) v(k) v ( k ) . Under the condition (35), the left-hand side of (38) equals the left-hand side of (40), which yields (40).
When the number of candidate basis functions is N = T N=T N = T and the selection matrix is S = I m T \mathcal{S}=I_{mT} S = I m T , Q S Q_{\mathcal{S}} Q S , defined in (24),
becomes Q S = I m ⊗ Φ T Q_S = I_m \otimes\Phi^{\mathsf{T}} Q S = I m ⊗ Φ T , which is an m T × m T mT \times mT m T × m T matrix and is invertible by Lemma 5. Hence its image is Im ( Q S ) = R m T \operatorname{Im}(Q_S) = \mathbb{R}^{mT} Im ( Q S ) = R m T . For any mean input sequence U ∈ R m × T U \in\mathbb{R}^{m \times T} U ∈ R m × T , setting the mean coefficient to ϖ S = Q S − 1 vec ( U T ) \varpi_S = Q_S^{-1}\operatorname{vec}(U^{\mathsf{T}}) ϖ S = Q S − 1 vec ( U T ) gives (26). Likewise, (27) and (28) hold for U ~ \widetilde{U} U and U ^ \widehat{U} U .
With these preparations, we give the proof of Theorem 3. Proof of Theorem 3: 1) The matrix P S ( k ) P_S(k) P S ( k ) , defined in (23), becomes P S ( k ) = I m ⊗ L ( k ) T P_S(k) = I_m \otimes L(k)^{\mathsf{T}} P S ( k ) = I m ⊗ L ( k ) T . Hence, by the mixed-product property of the Kronecker product,
∑ k = 0 T − 1 P S ( k ) T Σ v − 1 P S ( k ) = Σ v − 1 ⊗ ∑ k = 0 T − 1 L ( k ) L ( k ) T = Σ v − 1 ⊗ Φ Φ T . \sum_{k=0}^{T-1} P_S(k)^{\mathsf{T}}\Sigma_v^{-1}P_S(k) = \Sigma_v^{-1} \otimes\sum_{k=0}^{T-1} L(k)L(k)^{\mathsf{T}}
= \Sigma_v^{-1} \otimes\Phi\Phi^{\mathsf{T}}. k = 0 ∑ T − 1 P S ( k ) T Σ v − 1 P S ( k ) = Σ v − 1 ⊗ k = 0 ∑ T − 1 L ( k ) L ( k ) T = Σ v − 1 ⊗ Φ Φ T .
By 2) of Lemma 4, the square matrix Φ \Phi Φ , defined in (25), is invertible. Hence (35) gives the covariance matrix Σ S = Σ v ⊗ ( Φ Φ T ) − 1 \Sigma_S = \Sigma_v \otimes(\Phi\Phi^{\mathsf{T}})^{-1} Σ S = Σ v ⊗ ( Φ Φ T ) − 1 . The sampled input vector V = Q S ϑ S \mathcal{V} = Q_S\vartheta_S V = Q S ϑ S follows a Gaussian distribution. Using the expansion (28), its mean is Q S ϖ ^ S = vec ( U ^ T ) Q_S\widehat{\varpi}_S = \operatorname{vec}(\widehat{U}^{\mathsf{T}}) Q S ϖ S = vec ( U T ) , and its covariance matrix is
Q S Σ S Q S T = Σ v ⊗ Φ T ( Φ Φ T ) − 1 Φ = Σ v ⊗ I T . Q_S\Sigma_S Q_S^{\mathsf{T}} = \Sigma_v \otimes\Phi^{\mathsf{T}}(\Phi\Phi^{\mathsf{T}})^{-1}\Phi= \Sigma_v \otimes I_T. Q S Σ S Q S T = Σ v ⊗ Φ T ( Φ Φ T ) − 1 Φ = Σ v ⊗ I T .
This means that each column, the sampled input v ( k ) v(k) v ( k ) , independently follows N ( u ^ ( k ) , Σ v ) \mathcal{N}(\widehat{u}(k),\Sigma_v) N ( u ( k ) , Σ v ) , and thus the sampled input sequence V \mathcal{V} V follows the initial estimate distribution Q ^ \widehat{Q} Q .
By 3) of Lemma 7, (27) and (28) hold for any u ~ ( k ) , u ^ ( k ) \widetilde{u}(k),\widehat{u}(k) u ( k ) , u ( k ) . Hence, by 2) of Lemma 7, the weight w S ( ϑ S i ) w_S(\vartheta_S^i) w S ( ϑ S i ) for the selected coefficient ϑ S i \vartheta_S^i ϑ S i equals the weight w ( V i ) w(\mathcal{V}^i) w ( V i ) for the sampled input sequence V i \mathcal{V}^i V i . Multiplying ϖ ^ S \widehat{\varpi}_S ϖ S obtained in Algorithm 2 by Q S Q_S Q S , defined in (24), yields
Q S ϖ ^ S = ∑ i = 1 M w ( V i ) vec ( V i T ) ∑ i = 1 M w ( V i ) = vec ( U ^ † T ) . Q_S\widehat{\varpi}_S = \frac{\sum_{i=1}^{M} w(\mathcal{V}^i)\operatorname{vec}(\mathcal{V}^{i\mathsf{T}})}{\sum_{i=1}^{M}w(\mathcal{V}^i)} = \operatorname{vec}(\widehat{U}^{\dagger\mathsf{T}}). Q S ϖ S = ∑ i = 1 M w ( V i ) ∑ i = 1 M w ( V i ) vec ( V i T ) = vec ( U † T ) .
Since the input P S ( 0 ) ϖ ^ S P_S(0)\widehat{\varpi}_S P S ( 0 ) ϖ S applied in Algorithm 2 is the input at time 0 extracted from the vector Q S ϖ ^ S Q_S\widehat{\varpi}_S Q S ϖ S , it equals the input u ^ † ( 0 ) \widehat{u}^{\dagger}(0) u † ( 0 ) of MPPI. ■
Remark 2: Theorem 3 states the equality of u ^ † ( 0 ) \widehat{u}^{\dagger}(0) u † ( 0 ) in the sense of distribution. Conventional MPPI draws the sampled input vector V \mathcal{V} V directly from Q ^ \widehat{Q} Q , whereas Laguerre-MPPI draws the selected coefficient ϑ S \vartheta_S ϑ S from Q ^ S \widehat{Q}_S Q S and converts it into V = Q S ϑ S \mathcal{V} = Q_S\vartheta_S V = Q S ϑ S . As stated in 1) of Theorem 3, the converted V \mathcal{V} V follows Q ^ \widehat{Q} Q . The conversion by Q S Q_S Q S therefore moves each sample point without changing the distribution. Hence the samples of Laguerre-MPPI are interpreted as samples drawn from Q ^ \widehat{Q} Q with a random seed different from that of conventional MPPI. In particular, we let a = 0 a = 0 a = 0 in the basis function l i ( k ) l_i(k) l i ( k ) , defined in (18). This gives Q S = I m T Q_S = I_{mT} Q S = I m T and V = ϑ S \mathcal{V} = \vartheta_S V = ϑ S . Therefore, the samples of the two algorithms are equal even up to the sample points.
The main features of Laguerre-MPPI include smooth input generation and decoupling of the search dimension from the prediction horizon T T T . This subsection compares Laguerre-MPPI with existing variants of MPPI that share either of these features.
The first group of studies shapes the frequency content of the sampled input sequence to suppress chattering. Vlahov et al. [12 ] replaced the white Gaussian noise of MPPI with colored noise to promote low-frequency components in the sampled input sequence. LP-MPPI [17 ] applies a low-pass filter in the sampling process and removes the high-frequency components of the sampled noise. SMPPI [22 ] lifts the input space and adds an input cost that penalizes rough input sequences. These methods smooth the input, but they still sample the input at each time step in the prediction horizon. Hence the number of sampled variables remains m T mT m T , and the curse of dimensionality for long horizons remains.
The second group of studies reduces the search dimension by sampling a small number of parameters and interpolating the input sequence from them. Alvarez-Padilla et al. [5 ] achieved real-time whole-body control of quadruped robots by sampling four knots for each joint and interpolating them with a cubic spline. This spline representation reduces the search space and also smooths the input. Tao et al. [33 ] compared cubic spline, Bézier, and piecewise linear parameterizations in MPPI for legged robots and reported that low-dimensional structured sampling is important for this application. Schramm et al. [23 ] parameterized the joint references by cubic Hermite splines, and MuJoCo MPC [34 ] represents action trajectories by spline knots. In [5 ] , the knots are evenly distributed over the prediction horizon, and hence the input is represented with the same resolution over the whole horizon. Agentic MPC [35 ] represented the input sequence using Fourier basis functions and implemented MPPI by sampling in the coefficient space. This approach shares the central idea of Laguerre-MPPI: reducing the search dimension through a basis representation of the input sequence. However, [35 ] did not provide a theoretical analysis for the resulting control method.
Laguerre-MPPI belongs to the second group and differs from the existing methods in three aspects. First, the exponential decay of the Laguerre basis functions provides a finer representation of the control input near the beginning of the prediction horizon and a coarser representation toward its end, as shown in Section III-A. This allocation of resolution is well suited to the receding-horizon framework, in which only the first input is applied to the plant. Second, since the basis functions have low-pass characteristics for any ρ > 0 \rho> 0 ρ > 0 and every sampled input sequence is a linear combination of them, Laguerre-MPPI intrinsically yields the smooth input sequences that the first group aims at, without requiring an auxiliary filter or an additional cost term. Third, Laguerre-MPPI allows theoretical analysis of closed-loop stability and sampling error, as presented in the next two sections.
Stability Analysis
This section analyzes the closed-loop system under Laguerre-MPPI for linear plants with quadratic costs. Section IV-A sets up the analysis, and Section IV-B represents the closed-loop system under Laguerre-MPPI as a stochastic system and gives a stability condition in the infinite-sample limit. Section IV-C derives closed forms of the weighted moments of the selected coefficient ϑ S \vartheta_S ϑ S and obtains the optimal distribution Q S ∗ Q_S^* Q S ∗ and its mean, the optimal coefficient, explicitly.
Linear-Quadratic Setting
We restrict the analysis to the case where the nonlinear plant in (1) is given by the following linear time-invariant (LTI) system:
x ( k + 1 ) = A x ( k ) + B v ( k ) , (41) x(k+1)=Ax(k)+Bv(k), \tag*{(41)} x ( k + 1 ) = A x ( k ) + B v ( k ) , (41)
where A ∈ R n × n A\in\mathbb{R}^{n\times n} A ∈ R n × n and B ∈ R n × m B\in\mathbb{R}^{n\times m} B ∈ R n × m are constant system matrices. Furthermore, we replace the state cost (4) with the following quadratic cost:
S ( V ) = x ( T ) T Π x ( T ) + ∑ k = 0 T − 1 x ( k ) T W x ( k ) , (42) S(V)=x(T)^{\mathsf{T}}\Pi x(T)+\sum_{k=0}^{T-1}x(k)^{\mathsf{T}}Wx(k), \tag*{(42)} S ( V ) = x ( T ) T Π x ( T ) + k = 0 ∑ T − 1 x ( k ) T W x ( k ) , (42)
where Π , W ∈ R n × n \Pi,W\in\mathbb{R}^{n\times n} Π , W ∈ R n × n are the weight matrices satisfying Π ⪰ 0 \Pi\succeq0 Π ⪰ 0 and W ⪰ 0 W\succeq0 W ⪰ 0 . To address the regulation problem, we set the reference input as u ~ ( k ) ≡ 0 \tilde{u}(k)\equiv0 u ~ ( k ) ≡ 0 . Since Q S Q_S Q S , defined in (24), is of full column rank as stated in Lemma 5, the corresponding reference coefficient in (27) is ϖ ~ S = 0 \tilde{\varpi}_S=0 ϖ ~ S = 0 .
In the linear-quadratic setting, the state cost is expressed explicitly as follows. Substituting the relation (22) between the selected coefficient ϑ S \vartheta_S ϑ S and the sampled input v ( k ) v(k) v ( k ) into the solution of (41) with the initial state x ( 0 ) = x 0 x(0)=x_0 x ( 0 ) = x 0 , we have
x ( k ) = A k x 0 + B ˉ k S ϑ S , (43) x(k)=A^kx_0+\bar{B}_kS\vartheta_S, \tag*{(43)} x ( k ) = A k x 0 + B ˉ k S ϑ S , (43)
where B ˉ k ∈ R n × m N \bar{B}_k\in\mathbb{R}^{n\times mN} B ˉ k ∈ R n × m N is
B ˉ k : = ∑ j = 0 k − 1 A k − 1 − j B ( I m ⊗ L ( j ) T ) . (44) \bar{B}_k:=\sum_{j=0}^{k-1}A^{k-1-j}B(I_m\otimes L(j)^{\mathsf{T}}). \tag*{(44)} B ˉ k := j = 0 ∑ k − 1 A k − 1 − j B ( I m ⊗ L ( j ) T ) . (44)
Recalling S ϑ S ( ϑ S ) S_{\vartheta_S}(\vartheta_S) S ϑ S ( ϑ S ) , defined in (29), and substituting (43) into (42), we have the expression
S ϑ S ( ϑ S ) = ϑ S T H S ϑ S + 2 ( G S x 0 ) T ϑ S , (45) S_{\vartheta_S}(\vartheta_S)=\vartheta_S^{\mathsf{T}}H_S\vartheta_S+2(G_Sx_0)^{\mathsf{T}}\vartheta_S, \tag*{(45)} S ϑ S ( ϑ S ) = ϑ S T H S ϑ S + 2 ( G S x 0 ) T ϑ S , (45)
where H S ∈ R m d × m d H_S\in\mathbb{R}^{md\times md} H S ∈ R m d × m d and G S ∈ R m d × n G_S\in\mathbb{R}^{md\times n} G S ∈ R m d × n are given by
H S : = S T H S , (46) H_S:=S^{\mathsf{T}}HS, \tag*{(46)} H S := S T H S , (46)
G S : = S T G , (47) G_S:=S^{\mathsf{T}}G, \tag*{(47)} G S := S T G , (47)
and H ∈ R m N × m N H\in\mathbb{R}^{mN\times mN} H ∈ R m N × m N and G ∈ R m N × n G\in\mathbb{R}^{mN\times n} G ∈ R m N × n are defined as
H : = B ˉ T T Π B ˉ T + ∑ k = 0 T − 1 B ˉ k T W B ˉ k ⪰ 0 , (48) H:=\bar{B}_T^{\mathsf{T}}\Pi\bar{B}_T+\sum_{k=0}^{T-1}\bar{B}_k^{\mathsf{T}}W\bar{B}_k\succeq0, \tag*{(48)} H := B ˉ T T Π B ˉ T + k = 0 ∑ T − 1 B ˉ k T W B ˉ k ⪰ 0 , (48)
G : = B ˉ T T Π A T + ∑ k = 0 T − 1 B ˉ k T W A k . G:=\bar{B}_T^{\mathsf{T}}\Pi A^T+\sum_{k=0}^{T-1}\bar{B}_k^{\mathsf{T}}WA^k. G := B ˉ T T Π A T + k = 0 ∑ T − 1 B ˉ k T W A k .
The constant term in (42) is omitted in (45) since it does not affect the optimization of ϑ S \vartheta_S ϑ S .
Closed-Loop System and Stability
As in MPC, at each time step, Laguerre-MPPI optimizes the input sequence over the prediction horizon and applies only the first element of the sequence to the plant. Hence the analysis of the closed-loop system requires a distinction between the actual time and the time within the prediction horizon. We denote the actual time by k ∈ { 0 , 1 , … } k\in\{0,1,\ldots\} k ∈ { 0 , 1 , … } and the prediction time by τ ∈ { 0 , 1 , … , T − 1 } \tau\in\{0,1,\ldots,T-1\} τ ∈ { 0 , 1 , … , T − 1 } . Then, the predicted state and input τ \tau τ steps ahead of the actual time k k k are denoted by x ( τ ∣ k ) x(\tau|k) x ( τ ∣ k ) and u ( τ ∣ k ) u(\tau|k) u ( τ ∣ k ) , respectively. We further set the initial state of the prediction to the current state, i.e., x ( 0 ∣ k ) = x ( k ) x(0|k)=x(k) x ( 0∣ k ) = x ( k ) .
Recall that the finite-sample approximation ϖ ˉ S ( k ) \bar{\varpi}_S(k) ϖ ˉ S ( k ) of the optimal coefficient ϖ S ∗ ( k ) \varpi_S^*(k) ϖ S ∗ ( k ) is computed by Algorithm 2. Then, the mean input generated by Laguerre-MPPI is expressed as u † ( k ) = P S ( 0 ) ϖ ˉ S ( k ) u^\dagger(k)=P_S(0)\bar{\varpi}_S(k) u † ( k ) = P S ( 0 ) ϖ ˉ S ( k ) . The following theorem characterizes the resulting closed-loop system as a stochastic system governed by state-feedback control with additive stochastic noise.
Theorem 4. Consider the LTI system (41) and Laguerre-MPPI under the quadratic cost (42). Then, the following three statements hold.
The optimal coefficient ϖ S ∗ ( k ) \varpi_S^*(k) ϖ S ∗ ( k ) is given by
ϖ S ∗ ( k ) = − ( H S + λ 2 Σ S − 1 ) − 1 G S x ( k ) . (49) \varpi_S^*(k)=-\left(H_S+\frac{\lambda}{2}\Sigma_S^{-1}\right)^{-1}G_Sx(k). \tag*{(49)} ϖ S ∗ ( k ) = − ( H S + 2 λ Σ S − 1 ) − 1 G S x ( k ) . (49) The mean input generated by Laguerre-MPPI at time k k k is given by
u † ( k ) = − K ( S ) x ( k ) + ε M ( k ) , (50) u^\dagger(k)=-K(S)x(k)+\varepsilon_M(k), \tag*{(50)} u † ( k ) = − K ( S ) x ( k ) + ε M ( k ) , (50) where K ( S ) K(S) K ( S ) and ε M ( k ) \varepsilon_M(k) ε M ( k ) are given by
K ( S ) : = P S ( 0 ) ( H S + λ 2 Σ S − 1 ) − 1 G S , (51) K(S):=P_S(0)\left(H_S+\frac{\lambda}{2}\Sigma_S^{-1}\right)^{-1}G_S, \tag*{(51)} K ( S ) := P S ( 0 ) ( H S + 2 λ Σ S − 1 ) − 1 G S , (51) ε M ( k ) : = P S ( 0 ) ( ϖ ˉ S ( k ) − ϖ S ∗ ( k ) ) , (52) \varepsilon_M(k):=P_S(0)\left(\bar{\varpi}_S(k)-\varpi_S^*(k)\right), \tag*{(52)} ε M ( k ) := P S ( 0 ) ( ϖ ˉ S ( k ) − ϖ S ∗ ( k ) ) , (52) respectively.
For any state x ( k ) x(k) x ( k ) and any initial estimate coefficient ϖ ˉ S ( k ) \bar{\varpi}_S(k) ϖ ˉ S ( k ) , ε M ( k ) → 0 \varepsilon_M(k)\to0 ε M ( k ) → 0 almost surely as M → ∞ M\to\infty M → ∞ .
The proof of Theorem 4 is given in Section IV-C.
The finite-sample approximation ϖ ˉ S ∗ ( k ) \bar{\varpi}_S^*(k) ϖ ˉ S ∗ ( k ) in Theorem 4 determines the predicted input sequence within the prediction horizon,
u † ( τ ∣ k ) = P S ( τ ) ϖ ˉ S † ( k ) , τ ∈ { 0 , 1 , … , T − 1 } , (53) u^\dagger(\tau|k)=P_S(\tau)\bar{\varpi}_S^\dagger(k),\quad\tau\in\{0,1,\ldots,T-1\}, \tag*{(53)} u † ( τ ∣ k ) = P S ( τ ) ϖ ˉ S † ( k ) , τ ∈ { 0 , 1 , … , T − 1 } , (53)
where P S ( τ ) P_S(\tau) P S ( τ ) is defined in (23). Laguerre-MPPI applies only the first input u † ( k ) = u † ( 0 ∣ k ) u^\dagger(k)=u^\dagger(0|k) u † ( k ) = u † ( 0∣ k ) of (53). As in MPC, the state is updated to x ( k + 1 ) x(k+1) x ( k + 1 ) , the prediction horizon is shifted by one step, and the finite-sample approximation ϖ ˉ S ∗ ( k + 1 ) \bar{\varpi}_S^*(k+1) ϖ ˉ S ∗ ( k + 1 ) is computed with the state x ( k + 1 ) x(k+1) x ( k + 1 ) as the initial state.
Statement 2) shows that the first input u † ( 0 ∣ k ) u^\dagger(0|k) u † ( 0∣ k ) of (53) is equivalently rewritten in the feedback form (50), as illustrated in Figure 3 . The feedback gain K ( S ) K(S) K ( S ) in the first term of (50) is determined only by the covariance matrix Σ S \Sigma_S Σ S , the temperature parameter λ \lambda λ , and the matrices P S ( 0 ) P_S(0) P S ( 0 ) , H S H_S H S , and G S G_S G S , defined in (23), (46), and (47), respectively. Hence, K ( S ) K(S) K ( S ) is time-invariant. The second term, the stochastic noise ε M ( k ) \varepsilon_M(k) ε M ( k ) , defined in (52), arises from the difference between the finite-sample approximation ϖ ‾ S ( k ) \overline{\varpi}_S(k) ϖ S ( k ) and the optimal coefficient ϖ S ∗ ( k ) \varpi_S^*(k) ϖ S ∗ ( k ) . It varies randomly with the generated samples. Hence Laguerre-MPPI applies the linear time-invariant state feedback − K ( S ) x ( k ) -K(S)x(k) − K ( S ) x ( k ) with additive stochastic noise. Substituting (50) into (41), we see that the closed-loop system is the stochastic system
Figure 3. Closed-loop system under Laguerre-MPPI (left) and its equivalent representation given by Theorem 4 (right).
x ( k + 1 ) = ( A − B K ( S ) ) x ( k ) + B ε M ( k ) . (54) x(k+1)=(A-BK(S))x(k)+B\varepsilon_M(k). \tag*{(54)} x ( k + 1 ) = ( A − B K ( S )) x ( k ) + B ε M ( k ) . (54)
Statement 3) shows that the stochastic noise ε M ( k ) \varepsilon_M(k) ε M ( k ) converges to zero as M → ∞ M \to\infty M → ∞ , and the closed-loop system becomes
x ( k + 1 ) = ( A − B K ( S ) ) x ( k ) . (55) x(k+1)=(A-BK(S))x(k). \tag*{(55)} x ( k + 1 ) = ( A − B K ( S )) x ( k ) . (55)
Thus, infinite-sample Laguerre-MPPI reduces to a linear time-invariant state feedback law. The following corollary presents the condition for closed-loop stability in this limit.
Corollary 1: Consider the control system composed of (41) and Laguerre-MPPI with the quadratic cost (42) in the infinite-sample limit. Then, the origin is asymptotically stable if and only if A − B K ( S ) A-BK(S) A − B K ( S ) is Schur stable, i.e.,
ρ ( A − B K ( S ) ) < 1. (56) \rho(A-BK(S))<1. \tag*{(56)} ρ ( A − B K ( S )) < 1. (56)
Remark 3: For the LTI system (41) with the quadratic cost (42), the expected state cost satisfies E Q S [ S ϑ S ( ϑ S ) ] = S ϑ S ( ϖ S ) + tr ( H S Σ S ) \mathbb{E}_{Q_S}[S_{\vartheta_S}(\vartheta_S)]=S_{\vartheta_S}(\varpi_S)+\operatorname{tr}(H_S\Sigma_S) E Q S [ S ϑ S ( ϑ S )] = S ϑ S ( ϖ S ) + tr ( H S Σ S ) . Hence the minimizer of (31) is given by (49). In particular, when Σ S \Sigma_S Σ S satisfies (35), 1) of Lemma 7 shows that the coefficient cost b S ( ϖ S ) b_S(\varpi_S) b S ( ϖ S ) becomes λ 2 ∑ k u ( k ) ⊤ Σ v − 1 u ( k ) \frac{\lambda}{2}\sum_k u(k)^\top\Sigma_v^{-1}u(k) 2 λ ∑ k u ( k ) ⊤ Σ v − 1 u ( k ) . In this case, infinite-sample Laguerre-MPPI reduces to an MPC that solves the finite-horizon LQ problem with input weight λ 2 Σ v − 1 \frac{\lambda}{2}\Sigma_v^{-1} 2 λ Σ v − 1 restricted to the subspace spanned by the selected basis functions, and it has the same structure as Laguerre-MPC [29 ] .
Note that the control law under Laguerre-MPPI, given by (50), depends on the selection matrix S S S . Consequently, the closed-loop stability can be lost depending on the basis selection. Section VI-C confirms this dependence with a numerical example.
Weighted Moments and Proof of Theorem 4
This subsection presents the proof of Theorem 4, stated in Section IV-B. As preparation, we derive the weighted moments of the selected coefficient ϑ S \vartheta_S ϑ S with respect to the initial estimate distribution Q ^ S \hat{Q}_S Q ^ S . Since S ϑ S ( ϑ S ) S_{\vartheta_S}(\vartheta_S) S ϑ S ( ϑ S ) in (45) is a quadratic form in ϑ S \vartheta_S ϑ S , the product w S p q ^ S w_S^p\hat{q}_S w S p q ^ S of the p p p -th power of the weight (34) and the density q ^ S \hat{q}_S q ^ S of Q ^ S \hat{Q}_S Q ^ S is proportional to a Gaussian probability density for any p > 0 p>0 p > 0 . To describe this Gaussian density, we define, for p > 0 p>0 p > 0 ,
Λ p : = Σ S − 1 + 2 p λ H S , (57) \Lambda_p:=\Sigma_S^{-1}+\frac{2p}{\lambda}H_S, \tag*{(57)} Λ p := Σ S − 1 + λ 2 p H S , (57)
b p : = 2 p λ G S x 0 − Σ S − 1 [ ( 1 − p ) ϖ ^ S + p ϖ ~ S ] , (58) b_p:=\frac{2p}{\lambda}G_Sx_0-\Sigma_S^{-1}\left[(1-p)\hat{\varpi}_S+p\tilde{\varpi}_S\right], \tag*{(58)} b p := λ 2 p G S x 0 − Σ S − 1 [ ( 1 − p ) ϖ ^ S + p ϖ ~ S ] , (58)
m p : = − Λ p − 1 b p , (59) m_p:=-\Lambda_p^{-1}b_p, \tag*{(59)} m p := − Λ p − 1 b p , (59)
Q p : = N ( m p , Λ p − 1 ) . (60) Q_p:=\mathcal{N}(m_p,\Lambda_p^{-1}). \tag*{(60)} Q p := N ( m p , Λ p − 1 ) . (60)
In addition, for simplicity of notation, we let
Z p : = E Q ^ S [ w S p ] . (61) Z_p:=\mathbb{E}_{\hat{Q}_S}[w_S^p]. \tag*{(61)} Z p := E Q ^ S [ w S p ] . (61)
The following lemma shows that dividing the product w S p q ^ S w_S^p\hat{q}_S w S p q ^ S by Z p Z_p Z p yields the density q p q_p q p of the Gaussian distribution Q p Q_p Q p . Hence m p m_p m p and Λ p − 1 \Lambda_p^{-1} Λ p − 1 are the mean and the covariance matrix of the normalized product w S p q ^ S / Z p w_S^p\hat{q}_S/Z_p w S p q ^ S / Z p , respectively. In particular, for p = 1 p=1 p = 1 , the Gaussian distribution Q 1 Q_1 Q 1 equals the optimal distribution Q S ∗ Q_S^* Q S ∗ . The vector − b p -b_p − b p is the coefficient vector of the linear term in the exponent of w S p q ^ S w_S^p\hat{q}_S w S p q ^ S . We use the case p = 1 p=1 p = 1 for the optimal coefficient in Theorem 4 and the case p = 2 p=2 p = 2 for the ESS in Section V.
Lemma 8: For p > 0 p>0 p > 0 , let Λ p \Lambda_p Λ p , b p b_p b p , m p m_p m p , Q p Q_p Q p , and Z p Z_p Z p be defined by (57)–(61). Then, the following five statements hold.
Z p Z_p Z p is given by
Z p = exp ( 1 2 b p ⊤ Λ p − 1 b p − 1 2 ϖ ^ S ⊤ Σ S − 1 ϖ ^ S ) ∣ Σ S ∣ 1 / 2 ∣ Λ p ∣ 1 / 2 , (62) Z_p=\frac{\exp\left(\frac{1}{2}b_p^\top\Lambda_p^{-1}b_p-\frac{1}{2}\hat{\varpi}_S^\top\Sigma_S^{-1}\hat{\varpi}_S\right)}{|\Sigma_S|^{1/2}|\Lambda_p|^{1/2}}, \tag*{(62)} Z p = ∣ Σ S ∣ 1/2 ∣ Λ p ∣ 1/2 exp ( 2 1 b p ⊤ Λ p − 1 b p − 2 1 ϖ ^ S ⊤ Σ S − 1 ϖ ^ S ) , (62) and Z p ∈ ( 0 , ∞ ) Z_p\in(0,\infty) Z p ∈ ( 0 , ∞ ) holds.
It holds that
q p ( ϑ S ) = w S p ( ϑ S ) q ^ S ( ϑ S ) Z p , (63) q_p(\vartheta_S)=\frac{w_S^p(\vartheta_S)\hat{q}_S(\vartheta_S)}{Z_p}, \tag*{(63)} q p ( ϑ S ) = Z p w S p ( ϑ S ) q ^ S ( ϑ S ) , (63) for any selected coefficient ϑ S ∈ R m d \vartheta_S\in\mathbb{R}^{md} ϑ S ∈ R m d . In particular, Q 1 = Q S ∗ Q_1=Q_S^* Q 1 = Q S ∗ , whose density is given by (32).
For any measurable function φ \varphi φ satisfying E Q p [ ∣ φ ( ϑ S ) ∣ ] < ∞ \mathbb{E}_{Q_p}[|\varphi(\vartheta_S)|]<\infty E Q p [ ∣ φ ( ϑ S ) ∣ ] < ∞ ,
E Q p [ φ ( ϑ S ) ] = E Q ^ S [ w S p φ ( ϑ S ) ] Z p . (64) \mathbb{E}_{Q_p}[\varphi(\vartheta_S)]=\frac{\mathbb{E}_{\hat{Q}_S}[w_S^p\varphi(\vartheta_S)]}{Z_p}. \tag*{(64)} E Q p [ φ ( ϑ S )] = Z p E Q ^ S [ w S p φ ( ϑ S )] . (64)
It holds that
m p = E Q ^ S [ w S p ϑ S ] Z p , (65) m_p=\frac{\mathbb{E}_{\widehat{Q}_S}[w_S^p\vartheta_S]}{Z_p}, \tag*{(65)} m p = Z p E Q S [ w S p ϑ S ] , (65)
Λ p − 1 + m p m p ⊤ = E Q ^ S [ w S p ϑ S ϑ S ⊤ ] Z p . (66) \Lambda_p^{-1}+m_pm_p^\top=\frac{\mathbb{E}_{\widehat{Q}_S}[w_S^p\vartheta_S\vartheta_S^\top]}{Z_p}. \tag*{(66)} Λ p − 1 + m p m p ⊤ = Z p E Q S [ w S p ϑ S ϑ S ⊤ ] . (66)
For any r ≥ 0 r\ge0 r ≥ 0 ,
E Q ^ S [ w S p ∥ ϑ S ∥ r ] < ∞ . (67) \mathbb{E}_{\widehat{Q}_S}[w_S^p\lVert\vartheta_S\rVert^r]<\infty. \tag*{(67)} E Q S [ w S p ∥ ϑ S ∥ r ] < ∞. (67)
Proof: See Appendix E. ■
Based on Lemma 8, we give the proof of Theorem 4. Recall that Lemma 8 holds for the initial state x 0 x_0 x 0 and the initial estimate coefficient ϖ ^ S \widehat{\varpi}_S ϖ S . In the following proof of the theorem, we use the lemma with x 0 x_0 x 0 and ϖ ^ S \widehat{\varpi}_S ϖ S replaced by x ( k ) x(k) x ( k ) and ϖ ^ S ( k ) \widehat{\varpi}_S(k) ϖ S ( k ) , respectively, since the predicted state satisfies x ( 0 ∣ k ) = x ( k ) x(0|k)=x(k) x ( 0∣ k ) = x ( k ) .
Proof of Theorem 4: 1) Applying (65) with p = 1 p=1 p = 1 and the definition (61) of Z 1 Z_1 Z 1 to the numerator and denominator of (33) gives ϖ S ∗ ( k ) = Z 1 m 1 / Z 1 = m 1 \varpi_S^*(k)=Z_1m_1/Z_1=m_1 ϖ S ∗ ( k ) = Z 1 m 1 / Z 1 = m 1 . Since the reference coefficient is ϖ ~ S = 0 \widetilde{\varpi}_S=0 ϖ S = 0 , (57) and (59) give
ϖ S ∗ ( k ) = m 1 = − ( H S + λ 2 Σ S − 1 ) − 1 G S x ( k ) , \varpi_S^*(k)=m_1=-\left(H_S+\frac{\lambda}{2}\Sigma_S^{-1}\right)^{-1}G_Sx(k), ϖ S ∗ ( k ) = m 1 = − ( H S + 2 λ Σ S − 1 ) − 1 G S x ( k ) ,
which equals (49).
By Algorithm 2, the input applied at time k k k is u † ( k ) = P S ( 0 ) ϖ S † ( k ) u^\dagger(k)=P_S(0)\varpi_S^\dagger(k) u † ( k ) = P S ( 0 ) ϖ S † ( k ) . Substituting ϖ S † ( k ) = ϖ S ∗ ( k ) + ( ϖ S † ( k ) − ϖ S ∗ ( k ) ) \varpi_S^\dagger(k)=\varpi_S^*(k)+(\varpi_S^\dagger(k)-\varpi_S^*(k)) ϖ S † ( k ) = ϖ S ∗ ( k ) + ( ϖ S † ( k ) − ϖ S ∗ ( k )) gives
u † ( k ) = P S ( 0 ) ϖ S ∗ ( k ) + P S ( 0 ) ( ϖ S † ( k ) − ϖ S ∗ ( k ) ) . u^\dagger(k)=P_S(0)\varpi_S^*(k)+P_S(0)(\varpi_S^\dagger(k)-\varpi_S^*(k)). u † ( k ) = P S ( 0 ) ϖ S ∗ ( k ) + P S ( 0 ) ( ϖ S † ( k ) − ϖ S ∗ ( k )) .
The first term equals − K ( S ) x ( k ) -K(S)x(k) − K ( S ) x ( k ) , and the second term is the stochastic noise ϵ M ( k ) \epsilon_M(k) ϵ M ( k ) , defined in (52). Hence (50) follows.
This statement is the consistency of self-normalized importance sampling [36 , 37 ] . We show that the stochastic noise ϵ M ( k ) \epsilon_M(k) ϵ M ( k ) converges to zero almost surely as M → ∞ M\to\infty M → ∞ . The samples ϑ S 1 , … , ϑ S M \vartheta_S^1,\ldots,\vartheta_S^M ϑ S 1 , … , ϑ S M are generated independently from the initial estimate distribution Q ^ S \widehat{Q}_S Q S . We write the finite-sample approximation ϖ S † ( k ) \varpi_S^\dagger(k) ϖ S † ( k ) in Algorithm 2 as the ratio of the sample means of the numerator and the denominator,
ϖ S † ( k ) = N ‾ M D ‾ M , (68) \varpi_S^\dagger(k)=\frac{\overline{N}_M}{\overline{D}_M}, \tag*{(68)} ϖ S † ( k ) = D M N M , (68)
where N ‾ M \overline{N}_M N M and D ‾ M \overline{D}_M D M are given by
N ‾ M : = 1 M ∑ i = 1 M w S ( ϑ S i ) ϑ S i , \overline{N}_M:=\frac{1}{M}\sum_{i=1}^{M}w_S(\vartheta_S^i)\vartheta_S^i, N M := M 1 i = 1 ∑ M w S ( ϑ S i ) ϑ S i ,
D ‾ M : = 1 M ∑ i = 1 M w S ( ϑ S i ) , \overline{D}_M:=\frac{1}{M}\sum_{i=1}^{M}w_S(\vartheta_S^i), D M := M 1 i = 1 ∑ M w S ( ϑ S i ) ,
respectively. Since w S w_S w S and D ‾ M \overline{D}_M D M are positive, (68) is always well defined.
By 5) of Lemma 8, E Q ^ S [ w S ] < ∞ \mathbb{E}_{\widehat{Q}_S}[w_S]<\infty E Q S [ w S ] < ∞ and E Q ^ S [ w S ∥ ϑ S ∥ ] < ∞ \mathbb{E}_{\widehat{Q}_S}[w_S\lVert\vartheta_S\rVert]<\infty E Q S [ w S ∥ ϑ S ∥] < ∞ . Hence the weights w S ( ϑ S i ) w_S(\vartheta_S^i) w S ( ϑ S i ) and each entry of w S ( ϑ S i ) ϑ S i w_S(\vartheta_S^i)\vartheta_S^i w S ( ϑ S i ) ϑ S i are integrable independent and identically distributed random variables. As M → ∞ M\to\infty M → ∞ , the strong law of large numbers, the definition (61) of Z 1 Z_1 Z 1 , and (65) yield
N ‾ M → E Q ^ S [ w S ϑ S ] = Z 1 m 1 a.s. , \overline{N}_M\to\mathbb{E}_{\widehat{Q}_S}[w_S\vartheta_S]=Z_1m_1\quad\text{a.s.}, N M → E Q S [ w S ϑ S ] = Z 1 m 1 a.s. ,
D ‾ M → E Q ^ S [ w S ] = Z 1 a.s. (69) \overline{D}_M\to\mathbb{E}_{\widehat{Q}_S}[w_S]=Z_1\quad\text{a.s.} \tag*{(69)} D M → E Q S [ w S ] = Z 1 a.s. (69)
Since Z 1 Z_1 Z 1 , defined in (61), is positive by 1) of Lemma 8, the ratio map ( N ‾ M , D ‾ M ) ↦ N ‾ M / D ‾ M (\overline{N}_M,\overline{D}_M)\mapsto\overline{N}_M/\overline{D}_M ( N M , D M ) ↦ N M / D M is continuous at the point ( Z 1 m 1 , Z 1 ) (Z_1m_1,Z_1) ( Z 1 m 1 , Z 1 ) . Hence, combining (68) with the limits (69), we see that the finite-sample approximation ϖ S † ( k ) \varpi_S^\dagger(k) ϖ S † ( k ) converges almost surely to the optimal coefficient m 1 = ϖ S ∗ ( k ) m_1=\varpi_S^*(k) m 1 = ϖ S ∗ ( k ) . Since the stochastic noise ϵ M ( k ) \epsilon_M(k) ϵ M ( k ) , defined in (52), is a linear map of the sampling error ϖ S † ( k ) − ϖ S ∗ ( k ) \varpi_S^\dagger(k)-\varpi_S^*(k) ϖ S † ( k ) − ϖ S ∗ ( k ) , it satisfies ϵ M ( k ) → 0 \epsilon_M(k)\to0 ϵ M ( k ) → 0 a.s. ■
Sampling Efficiency Analysis
For a finite number of samples M M M , the stochastic noise ϵ M \epsilon_M ϵ M , defined in (52), perturbs the closed-loop dynamics as described by (54). This section derives estimates of the asymptotic covariance of the sampling error ϖ S † − ϖ S ∗ \varpi_S^\dagger-\varpi_S^* ϖ S † − ϖ S ∗ and the asymptotic ESS ratio, and shows that they are characterized by a single quantity.
Effective Sample Size
To assess sampling efficiency, we examine the concentration of the importance weights. As the weights become concentrated on fewer samples, the number of samples that effectively contribute to the finite-sample approximation decreases. We measure the sampling efficiency by the ESS [16 , 38 ] , defined by
E S S : = ( ∑ i = 1 M w S ( ϑ S i ) ) 2 ∑ i = 1 M w S ( ϑ S i ) 2 . (70) \mathrm{ESS}:=\frac{\left(\sum_{i=1}^{M}w_S(\vartheta_S^i)\right)^2}{\sum_{i=1}^{M}w_S(\vartheta_S^i)^2}. \tag*{(70)} ESS := ∑ i = 1 M w S ( ϑ S i ) 2 ( ∑ i = 1 M w S ( ϑ S i ) ) 2 . (70)
The ESS takes values in the range 1 ≤ E S S ≤ M 1\le\mathrm{ESS}\le M 1 ≤ ESS ≤ M . It equals M M M when all weights are equal, whereas it equals 1 1 1 when the weights concentrate on a single sample. Hence, a larger ESS implies a higher sampling efficiency. The ESS approximately represents the number of independent samples from the optimal distribution Q S ∗ \mathbb{Q}_S^* Q S ∗ to which the M M M weighted samples are equivalent [36 , 38 ] . In the following, we fix the state x ( k ) x(k) x ( k ) and the initial estimate coefficient ϖ ^ S ( k ) \widehat{\varpi}_S(k) ϖ S ( k ) at time k k k , and denote the difference between ϖ ^ S \widehat{\varpi}_S ϖ S and the optimal coefficient ϖ S ∗ \varpi_S^* ϖ S ∗ by
ν : = ϖ ^ S − ϖ S ∗ . (71) \nu:=\widehat{\varpi}_S-\varpi_S^*. \tag*{(71)} ν := ϖ S − ϖ S ∗ . (71)
Recalling Z p Z_p Z p of (61), we define
κ S : = Z 2 Z 1 2 . (72) \kappa^S:=\frac{Z_2}{Z_1^2}. \tag*{(72)} κ S := Z 1 2 Z 2 . (72)
Remark 4: The quantity κ S \kappa^S κ S is the second moment of the normalized weight w S / Z 1 w_S/Z_1 w S / Z 1 under the initial estimate distribution Q ^ S \widehat{Q}_S Q S . A small κ S \kappa^S κ S is desirable since κ S \kappa^S κ S measures the nonuniformity of the weights.
The following theorem is obtained by applying the asymptotic theory of self-normalized importance sampling [16], [36 ] to Laguerre-MPPI. It shows that the asymptotic covariance of the sampling error ϖ S † − ϖ S ∗ \varpi_S^\dagger-\varpi_S^* ϖ S † − ϖ S ∗ scales with κ S \kappa^S κ S and that the asymptotic ESS ratio equals 1 / κ S 1/\kappa^S 1/ κ S , and it gives κ S \kappa^S κ S in closed form.
Theorem 5. Consider the LTI system (41) and Laguerre-MPPI under the quadratic cost (42) , and fix the state x ( k ) x(k) x ( k ) and the initial estimate coefficient ϖ ^ S ( k ) \widehat{\varpi}_S(k) ϖ S ( k ) at time k k k . Then, the following three statements hold.
(Asymptotic normality)
M ( ϖ S † − ϖ S ∗ ) → d N ( 0 , Ξ ( κ S ) ) , M → ∞ , \sqrt{M}(\varpi_S^\dagger-\varpi_S^*) \xrightarrow{d} \mathcal{N}(0,\Xi(\kappa^S)),\quad M\to\infty, M ( ϖ S † − ϖ S ∗ ) d N ( 0 , Ξ ( κ S )) , M → ∞ , where Ξ ( κ S ) \Xi(\kappa^S) Ξ ( κ S ) is given by
Ξ ( κ S ) : = κ S [ Λ 2 − 1 + ( m 2 − m 1 ) ( m 2 − m 1 ) ⊤ ] , (73) \Xi(\kappa^S):=\kappa^S\left[\Lambda_2^{-1}+(m_2-m_1)(m_2-m_1)^\top\right], \tag*{(73)} Ξ ( κ S ) := κ S [ Λ 2 − 1 + ( m 2 − m 1 ) ( m 2 − m 1 ) ⊤ ] , (73) and Λ 2 \Lambda_2 Λ 2 , m 1 m_1 m 1 and m 2 m_2 m 2 are defined by (57) and (59) with p = 1 , 2 p=1,2 p = 1 , 2 .
(Asymptotic ESS ratio)
E S S M ⟶ 1 κ S a.s., M → ∞ . \frac{\mathrm{ESS}}{M}\longrightarrow\frac{1}{\kappa^S}\quad\text{a.s.,}\quad M\to\infty. M ESS ⟶ κ S 1 a.s., M → ∞. (Closed form of κ S \kappa^S κ S )
κ S = κ 0 S exp ( 1 2 ν ⊤ Ψ ν ) , (74) \kappa^S=\kappa_0^S\exp\left(\frac{1}{2}\nu^\top\Psi\nu\right), \tag*{(74)} κ S = κ 0 S exp ( 2 1 ν ⊤ Ψ ν ) , (74) where Ψ ≻ 0 \Psi\succ0 Ψ ≻ 0 and κ 0 S \kappa_0^S κ 0 S are given by
Ψ : = Σ S − 1 + Σ S − 1 Λ 2 − 1 Σ S − 1 , (75) \Psi:=\Sigma_S^{-1}+\Sigma_S^{-1}\Lambda_2^{-1}\Sigma_S^{-1}, \tag*{(75)} Ψ := Σ S − 1 + Σ S − 1 Λ 2 − 1 Σ S − 1 , (75) κ 0 S : = ∣ I m d + 2 λ Σ S H S ∣ ∣ I m d + 4 λ Σ S H S ∣ 1 / 2 , (76) \kappa_0^S:=\frac{\left|I_{md}+\frac{2}{\lambda}\Sigma_SH_S\right|}{\left|I_{md}+\frac{4}{\lambda}\Sigma_SH_S\right|^{1/2}}, \tag*{(76)} κ 0 S := I m d + λ 4 Σ S H S 1/2 I m d + λ 2 Σ S H S , (76) respectively, and H S H_S H S is defined in (46) .
Proof. See Appendix F. ■
Remark 5: As shown in (68) , the finite-sample approximation ϖ S † \varpi_S^\dagger ϖ S † is the ratio of N ˉ M \bar{N}_M N ˉ M and D ˉ M \bar{D}_M D ˉ M , which are computed from the sampled coefficients ϑ S i \vartheta_S^i ϑ S i and their weights w S ( ϑ S i ) w_S(\vartheta_S^i) w S ( ϑ S i ) . Since the expectation of a ratio does not equal the ratio of the expectations in general, the mean and the covariance matrix of the sampling error ϖ S † − ϖ S ∗ \varpi_S^\dagger-\varpi_S^* ϖ S † − ϖ S ∗ are difficult to obtain directly. Rewriting ϖ S † \varpi_S^\dagger ϖ S † around the limits Z 1 m 1 Z_1m_1 Z 1 m 1 and Z 1 Z_1 Z 1 of N ˉ M \bar{N}_M N ˉ M and D ˉ M \bar{D}_M D ˉ M yields
ϖ S † − ϖ S ∗ = 1 M 1 Z 1 ∑ i = 1 M w S ( ϑ S i ) ( ϑ S i − m 1 ) + ( N ˉ M − m 1 D ˉ M ) ( 1 D ˉ M − 1 Z 1 ) . (77) \varpi_S^\dagger-\varpi_S^*=\frac{1}{M}\frac{1}{Z_1}\sum_{i=1}^{M}w_S(\vartheta_S^i)(\vartheta_S^i-m_1)+(\bar{N}_M-m_1\bar{D}_M)\left(\frac{1}{\bar{D}_M}-\frac{1}{Z_1}\right). \tag*{(77)} ϖ S † − ϖ S ∗ = M 1 Z 1 1 i = 1 ∑ M w S ( ϑ S i ) ( ϑ S i − m 1 ) + ( N ˉ M − m 1 D ˉ M ) ( D ˉ M 1 − Z 1 1 ) . (77)
The first term is linear in N ˉ M \bar{N}_M N ˉ M and D ˉ M \bar{D}_M D ˉ M . This term is the sample mean of the independent random vectors w S ( ϑ S i ) ( ϑ S i − m 1 ) / Z 1 w_S(\vartheta_S^i)(\vartheta_S^i-m_1)/Z_1 w S ( ϑ S i ) ( ϑ S i − m 1 ) / Z 1 , and hence its mean is zero and its covariance matrix is Ξ ( κ S ) / M \Xi(\kappa^S)/M Ξ ( κ S ) / M . In the second term, both N ˉ M − m 1 D ˉ M \bar{N}_M-m_1\bar{D}_M N ˉ M − m 1 D ˉ M and 1 / D ˉ M − 1 / Z 1 1/\bar{D}_M-1/Z_1 1/ D ˉ M − 1/ Z 1 are of order 1 / M 1/\sqrt{M} 1/ M . Hence the second term is of order 1 / M 1/M 1/ M and converges to zero faster than the first term of order 1 / M 1/\sqrt{M} 1/ M . From this viewpoint, statement 1) is interpreted as follows: for sufficiently large M M M , the probability that the second term is not negligible compared with the first term is small, and the distribution of ϖ S † − ϖ S ∗ \varpi_S^\dagger-\varpi_S^* ϖ S † − ϖ S ∗ approaches N ( 0 , Ξ ( κ S ) / M ) \mathcal{N}(0,\Xi(\kappa^S)/M) N ( 0 , Ξ ( κ S ) / M ) of the first term. However, nothing is guaranteed about its mean and covariance matrix.
Remark 6: As stated in 1) and 2), a large κ S \kappa^S κ S reduces the asymptotic ESS M / κ S M/\kappa^S M / κ S and enlarges the asymptotic covariance matrix P S ( 0 ) Ξ ( κ S ) P S ( 0 ) ⊤ / M P_S(0)\Xi(\kappa^S)P_S(0)^\top/M P S ( 0 ) Ξ ( κ S ) P S ( 0 ) ⊤ / M of ϵ M ( k ) \epsilon_M(k) ϵ M ( k ) , defined in (52) . Hence a larger κ S \kappa^S κ S requires a larger number of samples M M M for the closed-loop system (54) to approximate the infinite-sample limit (55) . Statement 3) shows what makes κ S \kappa^S κ S large. As shown in (74) , κ S \kappa^S κ S is the product of the two factors κ 0 S \kappa_0^S κ 0 S and exp ( 1 2 ν ⊤ Ψ ν ) \exp(\frac{1}{2}\nu^\top\Psi\nu) exp ( 2 1 ν ⊤ Ψ ν ) . These two factors are interpreted as follows.
The factor κ 0 S \kappa_0^S κ 0 S , defined in (76) , represents the reduction of the ESS caused by the difference in covariance between the initial estimate distribution Q ^ S \widehat{Q}_S Q S and the optimal distribution Q S ∗ Q_S^* Q S ∗ . It equals κ 0 S \kappa_0^S κ 0 S for ν = 0 \nu=0 ν = 0 . Even in this case, the two distributions differ in covariance unless H S = 0 H_S=0 H S = 0 . As stated in 2) of Lemma 8, the covariance matrix of Q S ∗ = Q 1 Q_S^*=Q_1 Q S ∗ = Q 1 is Λ 1 − 1 \Lambda_1^{-1} Λ 1 − 1 , and Λ 1 ⪰ Σ S − 1 \Lambda_1\succeq\Sigma_S^{-1} Λ 1 ⪰ Σ S − 1 by (57) implies Λ 1 − 1 ⪯ Σ S \Lambda_1^{-1}\preceq\Sigma_S Λ 1 − 1 ⪯ Σ S . Hence the samples drawn from Q ^ S \widehat{Q}_S Q S spread more widely than those from Q S ∗ Q_S^* Q S ∗ , and the samples far from ϖ S ∗ \varpi_S^* ϖ S ∗ receive small weights. Appendix G shows the details.
The factor exp ( 1 2 ν ⊤ Ψ ν ) \exp(\frac{1}{2}\nu^\top\Psi\nu) exp ( 2 1 ν ⊤ Ψ ν ) represents the reduction of the ESS caused by the difference ν \nu ν between the means. When ϖ ^ S \widehat{\varpi}_S ϖ S deviates from ϖ S ∗ \varpi_S^* ϖ S ∗ , most samples lie away from the region where the optimal distribution has a large density, and the weights concentrate on the few samples near ϖ S ∗ \varpi_S^* ϖ S ∗ . Since Ψ \Psi Ψ , defined in (75) , is positive definite, this factor is no less than 1, equals 1 only for ν = 0 \nu=0 ν = 0 , and grows exponentially in ν ⊤ Ψ ν \nu^\top\Psi\nu ν ⊤ Ψ ν .
To relate the number of samples to the error from the infinite-sample limit, we impose the following assumption on the stochastic noise ϵ M ( k ) \epsilon_M(k) ϵ M ( k ) .
Assumption 4: The stochastic noise ϵ M ( k ) \epsilon_M(k) ϵ M ( k ) , defined in (52) , satisfies
E [ ϵ M ( k ) ∣ x ( k ) , ϖ ^ S ] = 0 , \mathbb{E}[\epsilon_M(k)\mid x(k),\widehat{\varpi}_S]=0, E [ ϵ M ( k ) ∣ x ( k ) , ϖ S ] = 0 , Cov [ ϵ M ( k ) ∣ x ( k ) , ϖ ^ S ] = 1 M P S ( 0 ) Ξ ( κ S ) P S ( 0 ) ⊤ . (78) \operatorname{Cov}[\epsilon_M(k)\mid x(k),\widehat{\varpi}_S]=\frac{1}{M}P_S(0)\Xi(\kappa^S)P_S(0)^\top. \tag*{(78)} Cov [ ϵ M ( k ) ∣ x ( k ) , ϖ S ] = M 1 P S ( 0 ) Ξ ( κ S ) P S ( 0 ) ⊤ . (78)
Assumption (78) replaces the mean and the covariance matrix of the sampling error ϖ S † − ϖ S ∗ \varpi_S^\dagger-\varpi_S^* ϖ S † − ϖ S ∗ by those of the first term of (77) . This is interpreted as assuming that the rare events in which the second term of (77) becomes large contribute negligibly to the mean and the covariance matrix.
Moreover, we let x n o m ( k ) x_{\mathrm{nom}}(k) x nom ( k ) and χ ( k ) : = x ( k ) − x n o m ( k ) \chi(k):=x(k)-x_{\mathrm{nom}}(k) χ ( k ) := x ( k ) − x nom ( k ) denote the state of the infinite-sample limit (55) with x n o m ( 0 ) = x ( 0 ) x_{\mathrm{nom}}(0)=x(0) x nom ( 0 ) = x ( 0 ) and the error between the actual state x ( k ) x(k) x ( k ) of the closed-loop system (54) and x n o m ( k ) x_{\mathrm{nom}}(k) x nom ( k ) , respectively. The following corollary gives a necessary condition on M M M for the root-mean-square error (RMSE) E [ ∥ χ ( k ) ∥ 2 ] 1 / 2 \mathbb{E}[\|\chi(k)\|^2]^{1/2} E [ ∥ χ ( k ) ∥ 2 ] 1/2 to stay within a tolerance χ t o l > 0 \chi_{\mathrm{tol}}>0 χ tol > 0 .
Corollary 2: Suppose that A − B K ( S ) A-BK(\mathcal{S}) A − B K ( S ) is Schur stable and that Assumption 4 holds. Let
Σ ϵ : = κ 0 S P S ( 0 ) Λ 2 − 1 P S ( 0 ) ⊤ , (79) \Sigma_\epsilon:=\kappa_0^S P_S(0)\Lambda_2^{-1}P_S(0)^\top, \tag*{(79)} Σ ϵ := κ 0 S P S ( 0 ) Λ 2 − 1 P S ( 0 ) ⊤ , (79) and Γ \Gamma Γ be the unique solution of the Lyapunov equation
Γ = ( A − B K ( S ) ) Γ ( A − B K ( S ) ) ⊤ + B Σ ϵ B ⊤ . (80) \Gamma=(A-BK(\mathcal{S}))\Gamma(A-BK(\mathcal{S}))^\top+B\Sigma_\epsilon B^\top. \tag*{(80)} Γ = ( A − B K ( S )) Γ ( A − B K ( S ) ) ⊤ + B Σ ϵ B ⊤ . (80)
If E [ ∥ χ ( k ) ∥ 2 ] ≤ χ t o l 2 \mathbb{E}[\lVert\chi(k)\rVert^2]\leq\chi_{\mathrm{tol}}^2 E [∥ χ ( k ) ∥ 2 ] ≤ χ tol 2 holds for all k ≥ 0 k\geq0 k ≥ 0 , then
M ≥ tr Υ χ t o l 2 . (81) M\geq\frac{\operatorname{tr}\Upsilon}{\chi_{\mathrm{tol}}^2}. \tag*{(81)} M ≥ χ tol 2 tr Υ . (81)
Proof: See Appendix H. ■
This shows that if M M M does not satisfy (81) , the RMSE E [ ∥ χ ( k ) ∥ 2 ] 1 / 2 \mathbb{E}[\lVert\chi(k)\rVert^2]^{1/2} E [∥ χ ( k ) ∥ 2 ] 1/2 exceeds χ t o l \chi_{\mathrm{tol}} χ tol at some time k k k . Hence, Corollary 2 provides a guideline on the number of samples required to accurately approximate the stochastic system (54) by the infinite-sample limit (55) . Note that even if M M M satisfies (81) , the RMSE may exceed χ t o l \chi_{\mathrm{tol}} χ tol at some time k k k . Since Σ ε \Sigma_{\varepsilon} Σ ε and Υ \Upsilon Υ depend only on the design parameters, this lower bound on M M M is evaluated before the samples are generated.
Search Dimension Reduction and the ESS Bound
As stated in 2) of Theorem 5, the asymptotic ESS ratio equals 1 / κ S 1/\kappa^{S} 1/ κ S . Hence the quantity κ S \kappa^{S} κ S , defined in (72) , indicates the sampling efficiency, and a smaller κ S \kappa^{S} κ S is desirable. As stated in 3) of Theorem 5, κ S \kappa^{S} κ S attains its minimum κ 0 S \kappa_{0}^{S} κ 0 S when the initial estimate coefficient ϖ ^ S \widehat{\varpi}_{S} ϖ S equals the optimal coefficient ϖ S ∗ \varpi_{S}^{*} ϖ S ∗ . This subsection shows that κ 0 S \kappa_{0}^{S} κ 0 S of Laguerre-MPPI is less than that of conventional MPPI, which implies the improved sampling efficiency of Laguerre-MPPI. In this subsection, the covariance matrix Σ S \Sigma_{S} Σ S satisfies (35) . Then, for fixed T T T , a a a , λ \lambda λ , Σ v \Sigma_{v} Σ v , and the system and cost matrices, κ 0 S \kappa_{0}^{S} κ 0 S is determined by the number N N N of candidate basis functions and the selection matrix S S S . To make this dependence explicit, we write
κ 0 ( N , S ) : = κ 0 S . \kappa_{0}(N,S):=\kappa_{0}^{S}. κ 0 ( N , S ) := κ 0 S .
Then, the following theorem holds.
Theorem 6: Suppose that Assumption 3 holds and that the covariance matrix Σ S \Sigma_{S} Σ S is given by (35) . Let μ 1 ( N , S ) ≥ ⋯ ≥ μ m d ( N , S ) \mu_{1}(N,S)\geq\cdots\geq\mu_{md}(N,S) μ 1 ( N , S ) ≥ ⋯ ≥ μ m d ( N , S ) be the eigenvalues of the symmetric positive semidefinite matrix Σ S 1 / 2 H S Σ S 1 / 2 \Sigma_{S}^{1/2}H_{S}\Sigma_{S}^{1/2} Σ S 1/2 H S Σ S 1/2 , where Σ S 1 / 2 \Sigma_{S}^{1/2} Σ S 1/2 is the symmetric square root of Σ S \Sigma_{S} Σ S , and let the function ψ \psi ψ be
ψ ( μ ) : = 1 + 2 μ / λ 1 + 4 μ / λ . (82) \psi(\mu):=\frac{1+2\mu/\lambda}{\sqrt{1+4\mu/\lambda}}. \tag*{(82)} ψ ( μ ) := 1 + 4 μ / λ 1 + 2 μ / λ . (82) Then, the following two statements hold.
κ 0 ( N , S ) \kappa_{0}(N,S) κ 0 ( N , S ) is given by
κ 0 ( N , S ) = ∏ i = 1 m d ψ ( μ i ( N , S ) ) . (83) \kappa_{0}(N,S)=\prod_{i=1}^{md}\psi\bigl(\mu_{i}(N,S)\bigr). \tag*{(83)} κ 0 ( N , S ) = i = 1 ∏ m d ψ ( μ i ( N , S ) ) . (83) For any selection matrix S S S ,
κ 0 ( N , S ) ≤ κ 0 ( T , I m T ) . (84) \kappa_{0}(N,S)\leq\kappa_{0}(T,I_{m_{T}}). \tag*{(84)} κ 0 ( N , S ) ≤ κ 0 ( T , I m T ) . (84) Proof: See Appendix I. ■
Remark 7: Recall from Theorem 3 that Laguerre-MPPI with N = T N=T N = T , S = I m T S=I_{m_{T}} S = I m T , and the covariance matrix satisfying (35) generates the sampled input sequence V V V following the initial estimate distribution Q ^ \widehat{Q} Q of conventional MPPI for any pole a a a . In addition, as stated in 2) and 3) of Lemma 7, its weight w S w_{S} w S equals the weight w w w of conventional MPPI, defined in (16) , evaluated at V V V . Hence, Laguerre-MPPI with these conditions reduce to conventional MPPI, and
κ 0 ( T , I m T ) \kappa_{0}(T,I_{m_{T}}) κ 0 ( T , I m T ) is the quantity corresponding to conventional MPPI.
As stated in 2) and 3) of Theorem 5, the asymptotic ESS ratio of Laguerre-MPPI is
lim M → ∞ E S S M = 1 κ 0 ( N , S ) exp ( − 1 2 ν T Ψ ν ) ≤ 1 κ 0 ( N , S ) a.s. , \lim_{M\to\infty}\frac{\mathrm{ESS}}{M}=\frac{1}{\kappa_{0}(N,S)}\exp\left(-\frac{1}{2}\nu^{\mathsf{T}}\Psi\nu\right)\leq\frac{1}{\kappa_{0}(N,S)}\quad\text{a.s.}, M → ∞ lim M ESS = κ 0 ( N , S ) 1 exp ( − 2 1 ν T Ψ ν ) ≤ κ 0 ( N , S ) 1 a.s. ,
where the equality holds if and only if ν = 0 \nu=0 ν = 0 , i.e., the initial estimate coefficient ϖ ^ S \widehat{\varpi}_{S} ϖ S equals the optimal coefficient ϖ S ∗ \varpi_{S}^{*} ϖ S ∗ . Hence 1 / κ 0 ( N , S ) 1/\kappa_{0}(N,S) 1/ κ 0 ( N , S ) is the maximum of the asymptotic ESS ratio over ϖ ^ S \widehat{\varpi}_{S} ϖ S . Moreover, 2) of Theorem 6 gives
1 κ 0 ( T , I m T ) ≤ 1 κ 0 ( N , S ) . \frac{1}{\kappa_{0}(T,I_{m_{T}})}\leq\frac{1}{\kappa_{0}(N,S)}. κ 0 ( T , I m T ) 1 ≤ κ 0 ( N , S ) 1 .
The left-hand side is the maximum for conventional MPPI. Therefore, for any pole a a a and any basis selection, the maximum of the asymptotic ESS ratio of Laguerre-MPPI is no less than that of conventional MPPI. This result quantifies the effect of the search dimension reduction, which keeps the samples dense in the coefficient space. Note that (84) compares the maxima attained at ν = 0 \nu=0 ν = 0 and does not imply the same ordering for each ϖ ^ S \widehat{\varpi}_{S} ϖ S .
Numerical Experiments
Sections VI-A and VI-B demonstrate through numerical experiments that Laguerre-MPPI produces smooth inputs and that its control performance is robust to the extension of the prediction horizon. Section VI-B also verifies numerically the inequality (84) in Theorem 6, which means that the maximum of the asymptotic ESS ratio of Laguerre-MPPI is no less than that of conventional MPPI. Section VI-C verifies that the stability condition (56) derived in the infinite-sample limit, also predicts whether the closed-loop system under finite samples converges or diverges. Section VI-D verifies the lower bound on the number of samples given in Corollary 2. Table III lists the parameters used in each experiment. In all experiments, the reference coefficient and the covariance matrix in the coefficient space are set to ϖ ~ S = 0 \widetilde{\varpi}_{S}=0 ϖ S = 0 and given by (35) , respectively.
Table III. Parameters of the numerical experiments
Obstacle Avoidance of a Mobile Robot
Consider the trajectory generation of a mobile robot described by the two-dimensional double integrator
x ( k + 1 ) = [ I 2 Δ I 2 0 I 2 ] x ( k ) + [ Δ 2 2 I 2 Δ I 2 ] u ( k ) , x(k+1)=
\begin{bmatrix}
I_{2} & \Delta I_{2}\\
0 & I_{2}
\end{bmatrix}x(k)+
\begin{bmatrix}
\frac{\Delta^{2}}{2}I_{2}\\
\Delta I_{2}
\end{bmatrix}u(k), x ( k + 1 ) = [ I 2 0 Δ I 2 I 2 ] x ( k ) + [ 2 Δ 2 I 2 Δ I 2 ] u ( k ) ,
where x = [ p x p y p ˙ x p ˙ y ] T x = [p_x\ p_y\ \dot{p}_x\ \dot{p}_y]^\mathsf{T} x = [ p x p y p ˙ x p ˙ y ] T is the state and u = [ u x u y ] T u = [u_x\ u_y]^\mathsf{T} u = [ u x u y ] T is the input. The initial and the target states are set to x 0 = [ 0 0 0 0 ] T x_0 = [0\ 0\ 0\ 0]^\mathsf{T} x 0 = [ 0 0 0 0 ] T and x r e f = [ 10 10 0 0 ] T x_{\mathrm{ref}} = [10\ 10\ 0\ 0]^\mathsf{T} x ref = [ 10 10 0 0 ] T , respectively. We let the state cost S ( V ) S(V) S ( V ) be given by
S ( V ) = ∑ τ = 0 T − 1 ( ∥ x ( τ ) − x r e f ∥ W 2 + α I ( x ( τ ) ) ) + ∥ x ( T ) − x r e f ∥ Π 2 + α I ( x ( T ) ) . S(V) = \sum_{\tau=0}^{T-1}\left(\lVert x(\tau)-x_{\mathrm{ref}}\rVert_W^2+\alpha\,\mathbb{I}(x(\tau))\right)+\lVert x(T)-x_{\mathrm{ref}}\rVert_\Pi^2+\alpha\,\mathbb{I}(x(T)). S ( V ) = τ = 0 ∑ T − 1 ( ∥ x ( τ ) − x ref ∥ W 2 + α I ( x ( τ )) ) + ∥ x ( T ) − x ref ∥ Π 2 + α I ( x ( T )) .
where I ( x ) \mathbb{I}(x) I ( x ) is the indicator function, i.e., I ( x ) = 1 \mathbb{I}(x)=1 I ( x ) = 1 if the position ( p x , p y ) (p_x,p_y) ( p x , p y ) is inside any obstacle and I ( x ) = 0 \mathbb{I}(x)=0 I ( x ) = 0 otherwise.
Figure 4 shows the resulting trajectories. As illustrated in Figure 4a , the trajectory generated by conventional MPPI is jagged and circles around the target. Since only 30 samples are used for the search dimension m T = 20 mT=20 m T = 20 , high-frequency components due to the sampling error remain in the computed inputs. As shown in Figure 4b , the trajectory generated by Laguerre-MPPI is smooth and shows no circling near the target. Two factors cause this difference. First, the search dimension is reduced to m d = 6 md=6 m d = 6 , which makes 30 samples relatively dense. Second, the basis functions with the pole a > 0 a>0 a > 0 have low-pass characteristics, which reduces the variation of the computed inputs.
Figure 4. Trajectories in obstacle avoidance. Red circles represent obstacles.
To compare the smoothness discussed above quantitatively, we evaluate the inputs over the interval in which both methods follow nearly the same course. The evaluation interval ends at the first time the robot comes within a distance of 0.5 of the target, and the relative input variation ∥ u ( k + 1 ) − u ( k ) ∥ 2 / ∥ u ( k ) ∥ 2 \lVert u(k+1)-u(k)\rVert_2/\lVert u(k)\rVert_2 ∥ u ( k + 1 ) − u ( k ) ∥ 2 / ∥ u ( k ) ∥ 2 is averaged over time and over 50 random seeds. The arrival time is 3.93 s for MPPI and 3.89 s for Laguerre-MPPI, which are nearly equal. Over this interval, the relative variation is 1.354 for MPPI and 0.837 for Laguerre-MPPI, which is approximately 38% smaller. This result confirms that Laguerre-MPPI yields smoother inputs than conventional MPPI.
We evaluate the step response of the one-dimensional double integrator
x ( k + 1 ) = [ 1 Δ 0 1 ] x ( k ) + [ Δ 2 2 Δ ] u ( k ) . x(k+1)=
\begin{bmatrix}
1 & \Delta\\
0 & 1
\end{bmatrix}x(k)+
\begin{bmatrix}
\frac{\Delta^2}{2}\\
\Delta
\end{bmatrix}u(k). x ( k + 1 ) = [ 1 0 Δ 1 ] x ( k ) + [ 2 Δ 2 Δ ] u ( k ) .
where x = [ p p ˙ ] T x=[p\ \dot{p}]^\mathsf{T} x = [ p p ˙ ] T represents the state consisting of the position p p p and the velocity p ˙ \dot{p} p ˙ . The initial and the target states are set to x 0 = [ 0 0 ] T x_0=[0\ 0]^\mathsf{T} x 0 = [ 0 0 ] T and x r e f = [ r 0 ] T x_{\mathrm{ref}}=[r\ 0]^\mathsf{T} x ref = [ r 0 ] T , respectively, with the target position r = 1 r=1 r = 1 . The state cost is given by (42) with the state x ( k ) x(k) x ( k ) replaced by the error x ( k ) − x r e f x(k)-x_{\mathrm{ref}} x ( k ) − x ref . We fix the number of samples M = 1000 M=1000 M = 1000 and the number of basis functions N = 5 N=5 N = 5 , and vary the horizon T T T from 5 to 35. The control performance is evaluated by the index
J I A E : = ∑ k = 0 K f ∣ r − p ( k ) ∣ . J_{\mathrm{IAE}} := \sum_{k=0}^{K_{\mathrm{f}}}|r-p(k)|. J IAE := k = 0 ∑ K f ∣ r − p ( k ) ∣.
where K f = 50 K_{\mathrm{f}}=50 K f = 50 .
The top panel of Figure 5 shows the mean and the ± 1 σ \pm1\sigma ± 1 σ range of the performance index J I A E J_{\mathrm{IAE}} J IAE over 20 random seeds. For horizons T ≤ 20 T\leq20 T ≤ 20 , MPPI and Laguerre-MPPI achieve comparable control performance, and the control performance of both methods improves as the horizon T T T increases. For horizons T > 20 T>20 T > 20 , the control performance of MPPI degrades substantially, and its variation across seeds also grows. In contrast, the control performance of Laguerre-MPPI degrades only slightly and varies little across seeds. This difference arises from the search dimension reduction. The search dimension of MPPI is m T mT m T and grows linearly with T T T , whereas that of Laguerre-MPPI remains m d = 5 md=5 m d = 5 regardless of the horizon T T T . Hence, Laguerre-MPPI is less susceptible to the curse of dimensionality caused by the extension of the horizon.
Figure 5. Prediction horizon T T T versus J I A E J_{\mathrm{IAE}} J IAE (top, mean and ± 1 σ \pm1\sigma ± 1 σ over 20 seeds) and versus κ 0 ( 5 , I 5 ) \kappa_0(5,I_5) κ 0 ( 5 , I 5 ) of Laguerre-MPPI and κ 0 ( T , I T ) \kappa_0(T,I_T) κ 0 ( T , I T ) of conventional MPPI (bottom).
The bottom panel of Figure 5 shows κ 0 ( 5 , I 5 ) \kappa_0(5,I_5) κ 0 ( 5 , I 5 ) of Laguerre-MPPI and κ 0 ( T , I T ) \kappa_0(T,I_T) κ 0 ( T , I T ) , which corresponds to conventional MPPI as stated in Remark 7, computed under the same setting. As stated in 2) of Theorem 6, κ 0 ( 5 , I 5 ) ≤ κ 0 ( T , I T ) \kappa_0(5,I_5)\leq\kappa_0(T,I_T) κ 0 ( 5 , I 5 ) ≤ κ 0 ( T , I T ) holds for all horizons, with equality at T = 5 T=5 T = 5 .
Basis Selection and Stability
We verify the stability test based on Corollary 1. Consider the plant system given by the oscillator
x ( k + 1 ) = [ cos Δ sin Δ − sin Δ cos Δ ] x ( k ) + [ 1 − cos Δ sin Δ ] u ( k ) , x(k+1)=\begin{bmatrix}\cos\Delta& \sin\Delta\\-\sin\Delta& \cos\Delta\end{bmatrix}x(k)+\begin{bmatrix}1-\cos\Delta\\\sin\Delta\end{bmatrix}u(k), x ( k + 1 ) = [ cos Δ − sin Δ sin Δ cos Δ ] x ( k ) + [ 1 − cos Δ sin Δ ] u ( k ) ,
where x = [ x 1 x 2 ] T = [ p p ˙ ] T x=[x_1\ x_2]^{\mathsf{T}}=[p\ \dot{p}]^{\mathsf{T}} x = [ x 1 x 2 ] T = [ p p ˙ ] T is the state, composed of the position p p p and the velocity p ˙ \dot{p} p ˙ . Table IV shows the spectral radius ρ ( A − B K ( S ) ) \rho(A-BK(S)) ρ ( A − B K ( S )) computed with the feedback gain (51) for 10 selection matrices S S S that select d = 3 d=3 d = 3 basis functions out of N = 5 N=5 N = 5 . Seven basis sets yield a spectral radius ρ < 1 \rho<1 ρ < 1 , which implies closed-loop stability, while the three basis sets { 2 , 3 , 4 } \{2,3,4\} { 2 , 3 , 4 } , { 2 , 3 , 5 } \{2,3,5\} { 2 , 3 , 5 } , and { 2 , 4 , 5 } \{2,4,5\} { 2 , 4 , 5 } yield a spectral radius ρ > 1 \rho>1 ρ > 1 , which implies instability. For example, for the set { 2 , 3 , 4 } \{2,3,4\} { 2 , 3 , 4 } , the eigenvalues of A − B K ( S ) A-BK(S) A − B K ( S ) in (55) are 1.02 ± 0.099 j 1.02\pm0.099\mathrm{j} 1.02 ± 0.099 j , which predicts oscillatory divergence.
Table IV. Basis selection and spectral radius.
Figure 6 shows the state trajectories generated by Laguerre-MPPI with the finite number of samples M = 10 5 M=10^5 M = 1 0 5 . In Figure 6 (a), the trajectories in the case that ρ < 1 \rho<1 ρ < 1 stay in a neighborhood of the origin, and the trajectories in the case that ρ > 1 \rho>1 ρ > 1 diverge with oscillation. The simulation results are consistent with the stability test summarized in Table IV . Figure 6 (b) shows an enlarged view of Figure 6 (a), allowing detailed inspection of the converging trajectories. In the figure,
Figure 6. Position x 1 x_1 x 1 in the closed-loop responses of Laguerre-MPPI (M = 10 5 M=10^5 M = 1 0 5 ). In (b), dotted lines show the response of the infinite-sample limit (55) .
the solid lines show representative trajectories generated by Laguerre-MPPI with a finite number of samples, whereas the dotted lines show the theoretical trajectories computed from (55) , corresponding to the infinite-sample limit. The two trajectories agree closely in each case. The error from the theoretical trajectory is caused by the stochastic noise ε M \varepsilon_M ε M , defined in (52) , and appears as small fluctuations near the origin.
Number of Samples and Finite-Sample Behavior
We verify the lower bound (81) in Corollary 2 for the stabilizing basis set { 1 , 3 , 4 } \{1,3,4\} { 1 , 3 , 4 } under the same setting as Section VI-C. For the tolerance χ t o l = 10 − 2 \chi_{\mathrm{tol}}=10^{-2} χ tol = 1 0 − 2 , the solution Υ \Upsilon Υ of (80) , computed from the design parameters, gives M ≥ 1009 M\geq1009 M ≥ 1009 in (81) . We set the number of samples to the smallest value M = 1009 M=1009 M = 1009 satisfying (81) and run the closed-loop simulation for 500 random seeds.
Figure 7 shows the results. The solid line is the RMSE E [ ∥ x ( k ) ∥ 2 ] 1 / 2 \mathbb{E}[\lVert x(k)\rVert^2]^{1/2} E [∥ x ( k ) ∥ 2 ] 1/2 estimated over the 500 seeds. The dashed line is ( tr Υ ( k ) / M ) 1 / 2 (\operatorname{tr}\Upsilon(k)/M)^{1/2} ( tr Υ ( k ) / M ) 1/2 , where Υ ( k ) \Upsilon(k) Υ ( k ) is computed by iterating the right-hand side of (80) from Υ ( 0 ) = 0 \Upsilon(0)=0 Υ ( 0 ) = 0 . As shown in the proof of Corollary 2, this curve is a lower bound on the RMSE at each time k k k and converges to ( tr Υ / M ) 1 / 2 (\operatorname{tr}\Upsilon/M)^{1/2} ( tr Υ/ M ) 1/2 as k → ∞ k\to\infty k → ∞ . The horizontal line shows the tolerance χ t o l \chi_{\mathrm{tol}} χ tol . As k k k increases, the lower bound converges to ( tr Υ / M ) 1 / 2 (\operatorname{tr}\Upsilon/M)^{1/2} ( tr Υ/ M ) 1/2 , which nearly equals χ t o l \chi_{\mathrm{tol}} χ tol for M = 1009 M=1009 M = 1009 . The measured RMSE is consistent with the lower bound over the whole time interval, and hence ( tr Υ / M ) 1 / 2 (\operatorname{tr}\Upsilon/M)^{1/2} ( tr Υ/ M ) 1/2 approximates the RMSE well in the steady state.
Figure 7. RMSE E [ ∥ χ ( k ) ∥ 2 ] 1 / 2 \mathbb{E}[\lVert\chi(k)\rVert^2]^{1/2} E [∥ χ ( k ) ∥ 2 ] 1/2 over 500 seeds for the basis set { 1 , 3 , 4 } \{1,3,4\} { 1 , 3 , 4 } and M = 1009 M=1009 M = 1009 (solid), its lower bound ( tr Υ ( k ) / M ) 1 / 2 (\operatorname{tr}\Upsilon(k)/M)^{1/2} ( tr Υ ( k ) / M ) 1/2 (dashed), and the tolerance χ t o l \chi_{\mathrm{tol}} χ tol (horizontal line).
Conclusions
We proposed Laguerre-MPPI, which expands the sampled inputs in Laguerre basis functions and samples the coefficients. In addition to developing the algorithm, we derived a closed-loop stability condition in the infinite-sample limit for linear systems with quadratic costs and analyzed the sampling error and the ESS under finite samples. Based on this analysis, we derived a lower bound on the number of samples for a prescribed deviation from the infinite-sample limit. The obstacle avoidance experiment showed that Laguerre-MPPI generates smoother inputs than conventional MPPI. The comparison with MPPI in step responses showed that Laguerre-MPPI is robust to long prediction horizons. We also showed that the closed-loop stability depends on the basis selection and verified the validity of the stability condition.
Future work includes a mean-square stability analysis of the stochastic system (54) [27 ] and a systematic basis-selection method that guarantees stability [39 ] .
Proof of Lemma 1
Proof:
F ( S , q ~ , λ ) = − λ ln ( E Q ~ [ exp ( − S ( V ) λ ) ] ) = − λ ln ( E Q [ exp ( − S ( V ) λ ) q ~ ( V ) q ( V ) ] ) . \begin{aligned}
\mathcal{F}(S,\tilde{q},\lambda)=-\lambda\ln\left(\mathbb{E}_{\tilde{Q}}\left[\exp\left(-\frac{S(V)}{\lambda}\right)\right]\right) \\
&=-\lambda\ln\left(\mathbb{E}_{Q}\left[\exp\left(-\frac{S(V)}{\lambda}\right)\frac{\tilde{q}(V)}{q(V)}\right]\right).
\end{aligned} F ( S , q ~ , λ ) = − λ ln ( E Q ~ [ exp ( − λ S ( V ) ) ] ) = − λ ln ( E Q [ exp ( − λ S ( V ) ) q ( V ) q ~ ( V ) ] ) .
Jensen’s inequality then gives
F ( S , q ~ , λ ) = − λ ln ( E Q [ exp ( − S ( V ) λ ) q ~ ( V ) q ( V ) ] ) ≤ − λ E Q [ ln ( exp ( − S ( V ) λ ) q ~ ( V ) q ( V ) ) ] . (85) \mathcal{F}(S,\tilde{q},\lambda)=-\lambda\ln\left(\mathbb{E}_{Q}\left[\exp\left(-\frac{S(V)}{\lambda}\right)\frac{\tilde{q}(V)}{q(V)}\right]\right)
\leq-\lambda\mathbb{E}_{Q}\left[\ln\left(\exp\left(-\frac{S(V)}{\lambda}\right)\frac{\tilde{q}(V)}{q(V)}\right)\right]. \tag*{(85)} F ( S , q ~ , λ ) = − λ ln ( E Q [ exp ( − λ S ( V ) ) q ( V ) q ~ ( V ) ] ) ≤ − λ E Q [ ln ( exp ( − λ S ( V ) ) q ( V ) q ~ ( V ) ) ] . (85)
The right-hand side of (85) satisfies
( R H S ) = − λ E Q [ − S ( V ) λ − ln ( q ( V ) q ~ ( V ) ) ] = E Q [ S ( V ) ] + λ D K L ( Q ∥ Q ~ ) . \begin{aligned}
(\mathrm{RHS})=-\lambda\mathbb{E}_{Q}\left[-\frac{S(V)}{\lambda}-\ln\left(\frac{q(V)}{\tilde{q}(V)}\right)\right] \\
&=\mathbb{E}_{Q}[S(V)]+\lambda D_{\mathrm{KL}}(Q\Vert\tilde{Q}).
\end{aligned} ( RHS ) = − λ E Q [ − λ S ( V ) − ln ( q ~ ( V ) q ( V ) ) ] = E Q [ S ( V )] + λ D KL ( Q ∥ Q ~ ) .
Therefore (6) holds.
Proof of Lemma 2
Proof: Applying the control distribution Q = N ( U , Σ v ) Q=\mathcal{N}(U,\Sigma_v) Q = N ( U , Σ v ) and the reference distribution Q ~ = N ( U ~ , Σ v ) \tilde{Q}=\mathcal{N}(\tilde{U},\Sigma_v) Q ~ = N ( U ~ , Σ v ) to the KL divergence D K L ( Q ∥ Q ~ ) D_{\mathrm{KL}}(Q\Vert\tilde{Q}) D KL ( Q ∥ Q ~ ) in (7) yields
D K L ( Q U ∥ Q ~ ) = 1 2 ∑ k = 0 T − 1 E Q U [ ( v ( k ) − u ~ ( k ) ) T Σ v − 1 ( v ( k ) − u ~ ( k ) ) − ( v ( k ) − u ( k ) ) T Σ v − 1 ( v ( k ) − u ( k ) ) ] . D_{\mathrm{KL}}(Q_U\Vert\tilde{Q})=\frac{1}{2}\sum_{k=0}^{T-1}\mathbb{E}_{Q_U}\left[(v(k)-\tilde{u}(k))^{\mathsf{T}}\Sigma_v^{-1}(v(k)-\tilde{u}(k))-(v(k)-u(k))^{\mathsf{T}}\Sigma_v^{-1}(v(k)-u(k))\right]. D KL ( Q U ∥ Q ~ ) = 2 1 k = 0 ∑ T − 1 E Q U [ ( v ( k ) − u ~ ( k ) ) T Σ v − 1 ( v ( k ) − u ~ ( k )) − ( v ( k ) − u ( k ) ) T Σ v − 1 ( v ( k ) − u ( k )) ] .
Using E Q U [ v ( k ) − u ( k ) ] = 0 \mathbb{E}_{Q_U}[v(k)-u(k)]=0 E Q U [ v ( k ) − u ( k )] = 0 , we obtain
D K L ( Q U ∥ Q ~ ) = 1 2 ∑ k = 0 T − 1 ( u ( k ) − u ~ ( k ) ) T Σ v − 1 ( u ( k ) − u ~ ( k ) ) . D_{\mathrm{KL}}(Q_U\Vert\tilde{Q})=\frac{1}{2}\sum_{k=0}^{T-1}(u(k)-\tilde{u}(k))^{\mathsf{T}}\Sigma_v^{-1}(u(k)-\tilde{u}(k)). D KL ( Q U ∥ Q ~ ) = 2 1 k = 0 ∑ T − 1 ( u ( k ) − u ~ ( k ) ) T Σ v − 1 ( u ( k ) − u ~ ( k )) .
Hence, under Assumptions 1 and 2,
E Q U [ S ( V ) ] + λ D K L ( Q U ∥ Q ~ ) = E Q U [ ϕ ( x ( T ) ) + ∑ k = 0 T − 1 L k ( x ( k ) , u ( k ) ) ] . \mathbb{E}_{Q_U}[S(V)]+\lambda D_{\mathrm{KL}}(Q_U\Vert\tilde{Q})
=\mathbb{E}_{Q_U}\left[\phi(x(T))+\sum_{k=0}^{T-1}\mathcal{L}_k(x(k),u(k))\right]. E Q U [ S ( V )] + λ D KL ( Q U ∥ Q ~ ) = E Q U [ ϕ ( x ( T )) + k = 0 ∑ T − 1 L k ( x ( k ) , u ( k )) ] .
Proof of Lemma 3
Proof: We transform the objective function of the relaxed problem for a distribution Q Q Q of arbitrary shape. Since exp ( − S ( V ) λ ) q ~ ( V ) = η q ∗ ( V ) \exp\left(-\frac{S(V)}{\lambda}\right)\tilde{q}(V)=\eta q^*(V) exp ( − λ S ( V ) ) q ~ ( V ) = η q ∗ ( V ) by (10),
E Q [ S ( V ) ] + λ D K L ( Q ∥ Q ~ ) = λ ∫ R m × T q ( V ) ln ( q ( V ) exp ( − S ( V ) λ ) q ~ ( V ) ) d V = λ ∫ R m × T q ( V ) ln ( q ( V ) q ∗ ( V ) ) d V − λ ln η = λ D K L ( Q ∥ Q ∗ ) + F ( S , q ~ , λ ) . \begin{aligned}
\mathbb{E}_{Q}[S(V)]+\lambda D_{\mathrm{KL}}(Q\Vert\tilde{Q})
=\lambda\int_{\mathbb{R}^{m\times T}}q(V)\ln\left(\frac{q(V)}{\exp\left(-\frac{S(V)}{\lambda}\right)\tilde{q}(V)}\right)\,\mathrm{d}V \\
&=\lambda\int_{\mathbb{R}^{m\times T}}q(V)\ln\left(\frac{q(V)}{q^*(V)}\right)\,\mathrm{d}V-\lambda\ln\eta\\
&=\lambda D_{\mathrm{KL}}(Q\Vert Q^*)+\mathcal{F}(S,\tilde{q},\lambda).
\end{aligned} E Q [ S ( V )] + λ D KL ( Q ∥ Q ~ ) = λ ∫ R m × T q ( V ) ln exp ( − λ S ( V ) ) q ~ ( V ) q ( V ) d V = λ ∫ R m × T q ( V ) ln ( q ∗ ( V ) q ( V ) ) d V − λ ln η = λ D KL ( Q ∥ Q ∗ ) + F ( S , q ~ , λ ) .
The last equality follows from the definition (5) of the free energy and (11). Next, by the two properties of the KL divergence
D K L ( F ∥ H ) ≥ 0 D_{\mathrm{KL}}(\mathbb{F}\Vert\mathbb{H})\geq0 D KL ( F ∥ H ) ≥ 0 ,
D K L ( F ∥ H ) = 0 ⇔ F = H D_{\mathrm{KL}}(\mathbb{F}\Vert\mathbb{H})=0\Leftrightarrow\mathbb{F}=\mathbb{H} D KL ( F ∥ H ) = 0 ⇔ F = H ,
the KL divergence satisfies D K L ( Q ∥ Q ∗ ) = 0 D_{\mathrm{KL}}(Q\Vert Q^*)=0 D KL ( Q ∥ Q ∗ ) = 0 only when the distribution equals the optimal distribution, Q = Q ∗ Q=Q^* Q = Q ∗ . Therefore the cost function J ( Q ) J(Q) J ( Q ) attains its minimum value, the free energy F ( S , q ~ , λ ) \mathcal{F}(S,\tilde{q},\lambda) F ( S , q ~ , λ ) , if and only if Q = Q ∗ Q=Q^* Q = Q ∗ .
Proof of Theorem 1
Proof: Let
w ~ : = exp ( − S ( V ) λ ) q ~ ( V ) q ( V ) . (86) \tilde{w}:=\exp\left(-\frac{S(V)}{\lambda}\right)\frac{\tilde{q}(V)}{q(V)}. \tag*{(86)} w ~ := exp ( − λ S ( V ) ) q ( V ) q ~ ( V ) . (86)
Then the density of the optimal distribution is q ∗ ( V ) = w ~ q ( V ) η q^*(V)=\frac{\tilde{w}q(V)}{\eta} q ∗ ( V ) = η w ~ q ( V ) . Therefore
E Q ∗ [ V ] = 1 η E Q ~ [ w ~ V ] , η = E Q ~ [ w ~ ] . \mathbb{E}_{Q^*}[V]=\frac{1}{\eta}\mathbb{E}_{\tilde{Q}}[\tilde{w}V],\qquad\eta=\mathbb{E}_{\tilde{Q}}[\tilde{w}]. E Q ∗ [ V ] = η 1 E Q ~ [ w ~ V ] , η = E Q ~ [ w ~ ] .
Applying the initial estimate distribution Q ~ = N ( U ~ , Σ ~ v ) \tilde{Q}=\mathcal{N}(\tilde{U},\tilde{\Sigma}_v) Q ~ = N ( U ~ , Σ ~ v ) and the reference distribution Q ~ = N ( U ~ , Σ ~ v ) \tilde{Q}=\mathcal{N}(\tilde{U},\tilde{\Sigma}_v) Q ~ = N ( U ~ , Σ ~ v ) , w ~ \tilde{w} w ~ defined in (86) factorizes as
w ~ ( V ) = exp ( − 1 2 ∑ k D k ) w ( V ) , \tilde{w}(V)=\exp\left(-\frac{1}{2}\sum_k D_k\right)w(V), w ~ ( V ) = exp ( − 2 1 k ∑ D k ) w ( V ) ,
D k : = u ~ ( k ) T Σ v − 1 u ~ ( k ) − u ^ ( k ) T Σ v − 1 u ^ ( k ) . D_k:=\tilde{u}(k)^{\mathsf{T}}\Sigma_v^{-1}\tilde{u}(k)-\hat{u}(k)^{\mathsf{T}}\Sigma_v^{-1}\hat{u}(k). D k := u ~ ( k ) T Σ v − 1 u ~ ( k ) − u ^ ( k ) T Σ v − 1 u ^ ( k ) .
Since the factor exp ( − 1 2 ∑ k D k ) \exp\left(-\frac{1}{2}\sum_kD_k\right) exp ( − 2 1 ∑ k D k ) does not depend on the sampled input sequence V V V ,
E Q ∗ [ V ] = E Q ^ [ w ~ V ] E Q ~ [ w ~ ] = E Q ^ [ w V ] E Q ^ [ w ] . \mathbb{E}_{Q^*}[V]=\frac{\mathbb{E}_{\hat{Q}}[\tilde{w}V]}{\mathbb{E}_{\tilde{Q}}[\tilde{w}]}=\frac{\mathbb{E}_{\hat{Q}}[wV]}{\mathbb{E}_{\hat{Q}}[w]}. E Q ∗ [ V ] = E Q ~ [ w ~ ] E Q ^ [ w ~ V ] = E Q ^ [ w ] E Q ^ [ w V ] .
Proof of Lemma 8
Proof. 1) Since Σ ^ S − 1 ≻ 0 \widehat{\Sigma}_{S}^{-1} \succ0 Σ S − 1 ≻ 0 , H S ⪰ 0 H_{S} \succeq0 H S ⪰ 0 , and p > 0 p>0 p > 0 , (57) gives Λ p ≻ 0 \Lambda_{p} \succ0 Λ p ≻ 0 . The outline of the proof is as follows. Since both the p p p -th power w S p w_{S}^{p} w S p of the weight and the density q ^ S \widehat{q}_{S} q S are exponentials of quadratic functions of the selected coefficient ϑ S \vartheta_{S} ϑ S , their product w S p q ^ S w_{S}^{p}\widehat{q}_{S} w S p q S is written as a constant multiple of a Gaussian probability density, which reduces Z p = E Q ^ S [ w S p ] Z_{p}=\mathbb{E}_{\widehat{Q}_{S}}[w_{S}^{p}] Z p = E Q S [ w S p ] defined in (61) to an expectation under Q p Q_{p} Q p defined in (60).
We rearrange the integrand w S p q ^ S w_{S}^{p}\widehat{q}_{S} w S p q S . By (34) and (45), the p p p -th power w S p w_{S}^{p} w S p of the weight is
w S p ( ϑ S ) = exp ( − p λ ( ∥ ϑ S ∥ H S 2 + 2 ( G S x 0 ) T ϑ S ) − p ( ϖ ^ S − ϖ ~ S ) T Σ ^ S − 1 ϑ S ) . (87) w_{S}^{p}(\vartheta_{S})=\exp\left(-\frac{p}{\lambda}\left(\lVert\vartheta_{S}\rVert_{H_{S}}^{2}+2(G_{S}x_{0})^{\mathsf{T}}\vartheta_{S}\right)-p(\widehat{\varpi}_{S}-\widetilde{\varpi}_{S})^{\mathsf{T}}\widehat{\Sigma}_{S}^{-1}\vartheta_{S}\right). \tag*{(87)} w S p ( ϑ S ) = exp ( − λ p ( ∥ ϑ S ∥ H S 2 + 2 ( G S x 0 ) T ϑ S ) − p ( ϖ S − ϖ S ) T Σ S − 1 ϑ S ) . (87)
The probability density of the initial estimate distribution Q ^ S \widehat{Q}_{S} Q S is
q ^ S ( ϑ S ) = c exp ( − 1 2 ∥ ϑ S − ϖ ^ S ∥ Σ ^ S − 1 2 ) , (88) \widehat{q}_{S}(\vartheta_{S})=c\exp\left(-\frac{1}{2}\lVert\vartheta_{S}-\widehat{\varpi}_{S}\rVert_{\widehat{\Sigma}_{S}^{-1}}^{2}\right), \tag*{(88)} q S ( ϑ S ) = c exp ( − 2 1 ∥ ϑ S − ϖ S ∥ Σ S − 1 2 ) , (88)
where
c : = ( 2 π ) − m d / 2 ∣ Σ S ∣ − 1 / 2 . (89) c:=(2\pi)^{-md/2}|\Sigma_{S}|^{-1/2}. \tag*{(89)} c := ( 2 π ) − m d /2 ∣ Σ S ∣ − 1/2 . (89)
Multiplying (87) by (88) and rearranging in the selected coefficient ϑ S \vartheta_{S} ϑ S with (57) and (58) yields
w S p ( ϑ S ) q ^ S ( ϑ S ) = c exp ( − 1 2 ∥ ϑ S ∥ Λ p 2 − b p T ϑ S − 1 2 ∥ ϖ ^ S ∥ Σ ^ S − 1 2 ) . (90) w_{S}^{p}(\vartheta_{S})\widehat{q}_{S}(\vartheta_{S})=c\exp\left(-\frac{1}{2}\lVert\vartheta_{S}\rVert_{\Lambda_{p}}^{2}-b_{p}^{\mathsf{T}}\vartheta_{S}-\frac{1}{2}\lVert\widehat{\varpi}_{S}\rVert_{\widehat{\Sigma}_{S}^{-1}}^{2}\right). \tag*{(90)} w S p ( ϑ S ) q S ( ϑ S ) = c exp ( − 2 1 ∥ ϑ S ∥ Λ p 2 − b p T ϑ S − 2 1 ∥ ϖ S ∥ Σ S − 1 2 ) . (90)
Completing the square in the exponent of (90) with m p m_{p} m p defined in (59) gives
− 1 2 ∥ ϑ S ∥ Λ p 2 − b p T ϑ S − 1 2 ∥ ϖ ^ S ∥ Σ ^ S − 1 2 = − 1 2 ∥ ϑ S − m p ∥ Λ p 2 + 1 2 ∥ b p ∥ Λ p − 1 2 − 1 2 ∥ ϖ ^ S ∥ Σ ^ S − 1 2 . -\frac{1}{2}\lVert\vartheta_{S}\rVert_{\Lambda_{p}}^{2}-b_{p}^{\mathsf{T}}\vartheta_{S}-\frac{1}{2}\lVert\widehat{\varpi}_{S}\rVert_{\widehat{\Sigma}_{S}^{-1}}^{2}
=-\frac{1}{2}\lVert\vartheta_{S}-m_{p}\rVert_{\Lambda_{p}}^{2}+\frac{1}{2}\lVert b_{p}\rVert_{\Lambda_{p}^{-1}}^{2}-\frac{1}{2}\lVert\widehat{\varpi}_{S}\rVert_{\widehat{\Sigma}_{S}^{-1}}^{2}. − 2 1 ∥ ϑ S ∥ Λ p 2 − b p T ϑ S − 2 1 ∥ ϖ S ∥ Σ S − 1 2 = − 2 1 ∥ ϑ S − m p ∥ Λ p 2 + 2 1 ∥ b p ∥ Λ p − 1 2 − 2 1 ∥ ϖ S ∥ Σ S − 1 2 .
Therefore
w S p ( ϑ S ) q ^ S ( ϑ S ) = { c exp ( 1 2 ∥ b p ∥ Λ p − 1 2 − 1 2 ∥ ϖ ^ S ∥ Σ ^ S − 1 2 ) } ⋅ exp ( − 1 2 ∥ ϑ S − m p ∥ Λ p 2 ) . (91) w_{S}^{p}(\vartheta_{S})\widehat{q}_{S}(\vartheta_{S})=
\left\{c\exp\left(\frac{1}{2}\lVert b_{p}\rVert_{\Lambda_{p}^{-1}}^{2}-\frac{1}{2}\lVert\widehat{\varpi}_{S}\rVert_{\widehat{\Sigma}_{S}^{-1}}^{2}\right)\right\}
\cdot\exp\left(-\frac{1}{2}\lVert\vartheta_{S}-m_{p}\rVert_{\Lambda_{p}}^{2}\right). \tag*{(91)} w S p ( ϑ S ) q S ( ϑ S ) = { c exp ( 2 1 ∥ b p ∥ Λ p − 1 2 − 2 1 ∥ ϖ S ∥ Σ S − 1 2 ) } ⋅ exp ( − 2 1 ∥ ϑ S − m p ∥ Λ p 2 ) . (91)
We now integrate (91) over R m d \mathbb{R}^{md} R m d using the Gaussian integral
∫ R m d exp ( − 1 2 ∥ ϑ S − m p ∥ Λ p 2 ) d ϑ S = ( 2 π ) m d / 2 ∣ Λ p ∣ − 1 / 2 . (92) \int_{\mathbb{R}^{md}}\exp\left(-\frac{1}{2}\lVert\vartheta_{S}-m_{p}\rVert_{\Lambda_{p}}^{2}\right)d\vartheta_{S}=(2\pi)^{md/2}|\Lambda_{p}|^{-1/2}. \tag*{(92)} ∫ R m d exp ( − 2 1 ∥ ϑ S − m p ∥ Λ p 2 ) d ϑ S = ( 2 π ) m d /2 ∣ Λ p ∣ − 1/2 . (92)
By the definition (61) of Z p Z_{p} Z p , (91), and (92),
Z p = ∫ R m d w S p ( ϑ S ) q ^ S ( ϑ S ) d ϑ S = c ( 2 π ) m d / 2 ∣ Λ p ∣ − 1 / 2 exp ( 1 2 ∥ b p ∥ Λ p − 1 2 − 1 2 ∥ ϖ ^ S ∥ Σ ^ S − 1 2 ) . \begin{aligned}
Z_{p}&=\int_{\mathbb{R}^{md}}w_{S}^{p}(\vartheta_{S})\widehat{q}_{S}(\vartheta_{S})\,d\vartheta_{S}\\
&=c(2\pi)^{md/2}|\Lambda_{p}|^{-1/2}\exp\left(\frac{1}{2}\lVert b_{p}\rVert_{\Lambda_{p}^{-1}}^{2}-\frac{1}{2}\lVert\widehat{\varpi}_{S}\rVert_{\widehat{\Sigma}_{S}^{-1}}^{2}\right).
\end{aligned} Z p = ∫ R m d w S p ( ϑ S ) q S ( ϑ S ) d ϑ S = c ( 2 π ) m d /2 ∣ Λ p ∣ − 1/2 exp ( 2 1 ∥ b p ∥ Λ p − 1 2 − 2 1 ∥ ϖ S ∥ Σ S − 1 2 ) .
Substituting c c c defined in (89) yields (62). The right-hand side of (62) is positive and finite.
Since the probability density of Q p Q_{p} Q p defined in (60) is
q p ( ϑ S ) = ( 2 π ) − m d / 2 ∣ Λ p ∣ − 1 / 2 exp ( − 1 2 ∥ ϑ S − m p ∥ Λ p 2 ) , (93) q_{p}(\vartheta_{S})=(2\pi)^{-md/2}|\Lambda_{p}|^{-1/2}\exp\left(-\frac{1}{2}\lVert\vartheta_{S}-m_{p}\rVert_{\Lambda_{p}}^{2}\right), \tag*{(93)} q p ( ϑ S ) = ( 2 π ) − m d /2 ∣ Λ p ∣ − 1/2 exp ( − 2 1 ∥ ϑ S − m p ∥ Λ p 2 ) , (93)
expressing the right-hand side of (91) obtained in the proof of 1) with the closed form (62) of Z p Z_{p} Z p and (93) yields (63). For p = 1 p=1 p = 1 , the density ratio in the proof of 4) of Theorem 2 shows that the product w S q ^ S w_{S}\widehat{q}_{S} w S q S equals exp ( − S ϑ S / λ ) q ~ S \exp(-S_{\vartheta_{S}}/\lambda)\widetilde{q}_{S} exp ( − S ϑ S / λ ) q S up to a positive constant factor independent of the selected coefficient ϑ S \vartheta_{S} ϑ S . The redefinition of S ϑ S S_{\vartheta_{S}} S ϑ S in (45) removes only a constant term and hence does not change the density q S ∗ q_{S}^{*} q S ∗ of the optimal distribution given by (32). Hence, by (32), the product w S q ^ S w_{S}\widehat{q}_{S} w S q S is proportional to the density q S ∗ q_{S}^{*} q S ∗ . By (63) with p = 1 p=1 p = 1 , the product w S q ^ S w_{S}\widehat{q}_{S} w S q S is also proportional to the density q 1 q_{1} q 1 . Since both q S ∗ q_{S}^{*} q S ∗ and q 1 q_{1} q 1 are probability densities, q 1 = q S ∗ q_{1}=q_{S}^{*} q 1 = q S ∗ , that is, Q 1 = Q ∗ Q_{1}=Q^{*} Q 1 = Q ∗ .
By (63), for any selected coefficient ϑ S \vartheta_{S} ϑ S ,
∣ w S p ( ϑ S ) φ ( ϑ S ) ∣ q ^ S ( ϑ S ) = Z p ∣ φ ( ϑ S ) ∣ q p ( ϑ S ) . (94) |w_{S}^{p}(\vartheta_{S})\varphi(\vartheta_{S})|\widehat{q}_{S}(\vartheta_{S})=Z_{p}|\varphi(\vartheta_{S})|q_{p}(\vartheta_{S}). \tag*{(94)} ∣ w S p ( ϑ S ) φ ( ϑ S ) ∣ q S ( ϑ S ) = Z p ∣ φ ( ϑ S ) ∣ q p ( ϑ S ) . (94)
By the assumption E Q p [ ∣ φ ( ϑ S ) ∣ ] < ∞ \mathbb{E}_{Q_{p}}[|\varphi(\vartheta_{S})|]<\infty E Q p [ ∣ φ ( ϑ S ) ∣ ] < ∞ and (94),
E Q ^ S [ ∣ w S p ( ϑ S ) φ ( ϑ S ) ∣ ] < ∞ , E Q p [ ∣ φ ( ϑ S ) ∣ ] < ∞ . \mathbb{E}_{\widehat{Q}_{S}}[|w_{S}^{p}(\vartheta_{S})\varphi(\vartheta_{S})|]<\infty,\qquad\mathbb{E}_{Q_{p}}[|\varphi(\vartheta_{S})|]<\infty. E Q S [ ∣ w S p ( ϑ S ) φ ( ϑ S ) ∣ ] < ∞ , E Q p [ ∣ φ ( ϑ S ) ∣ ] < ∞.
Hence both sides of (64) are finite, and by (63),
E Q ^ S [ w S p φ ( ϑ S ) ] = ∫ R m d w S p ( ϑ S ) φ ( ϑ S ) q ^ S ( ϑ S ) d ϑ S = Z p ∫ R m d φ ( ϑ S ) q p ( ϑ S ) d ϑ S = Z p E Q p [ φ ( ϑ S ) ] . \begin{aligned}
\mathbb{E}_{\widehat{Q}_{S}}[w_{S}^{p}\varphi(\vartheta_{S})]
&=\int_{\mathbb{R}^{md}}w_{S}^{p}(\vartheta_{S})\varphi(\vartheta_{S})\widehat{q}_{S}(\vartheta_{S})\,d\vartheta_{S}\\
&=Z_{p}\int_{\mathbb{R}^{md}}\varphi(\vartheta_{S})q_{p}(\vartheta_{S})\,d\vartheta_{S}\\
&=Z_{p}\mathbb{E}_{Q_{p}}[\varphi(\vartheta_{S})].
\end{aligned} E Q S [ w S p φ ( ϑ S )] = ∫ R m d w S p ( ϑ S ) φ ( ϑ S ) q S ( ϑ S ) d ϑ S = Z p ∫ R m d φ ( ϑ S ) q p ( ϑ S ) d ϑ S = Z p E Q p [ φ ( ϑ S )] .
The first and second moments of the Gaussian distribution Q p Q_{p} Q p are
E Q p [ ϑ S ] = m p , E Q p [ ϑ S ϑ S T ] = Λ p − 1 + m p m p T . (95) \mathbb{E}_{Q_{p}}[\vartheta_{S}]=m_{p},\qquad\mathbb{E}_{Q_{p}}[\vartheta_{S}\vartheta_{S}^{\mathsf{T}}]=\Lambda_{p}^{-1}+m_{p}m_{p}^{\mathsf{T}}. \tag*{(95)} E Q p [ ϑ S ] = m p , E Q p [ ϑ S ϑ S T ] = Λ p − 1 + m p m p T . (95)
both of which are finite. Applying (64) to φ ( ϑ S ) = ϑ S \varphi(\vartheta_{S})=\vartheta_{S} φ ( ϑ S ) = ϑ S and to each entry of ϑ S ϑ S T \vartheta_{S}\vartheta_{S}^{\mathsf{T}} ϑ S ϑ S T and substituting (95) yield (65) and (66).
Since all moments of a Gaussian distribution are finite, E Q p [ ∥ ϑ S ∥ r ] < ∞ \mathbb{E}_{Q_{p}}[\lVert\vartheta_{S}\rVert^{r}]<\infty E Q p [∥ ϑ S ∥ r ] < ∞ for any r ≥ 0 r\geq0 r ≥ 0 . Applying (64) to φ ( ϑ S ) = ∥ ϑ S ∥ r \varphi(\vartheta_{S})=\lVert\vartheta_{S}\rVert^{r} φ ( ϑ S ) = ∥ ϑ S ∥ r gives
E Q ^ S [ w S p ∥ ϑ S ∥ r ] = Z p E Q p [ ∥ ϑ S ∥ r ] < ∞ , \mathbb{E}_{\widehat{Q}_{S}}[w_{S}^{p}\lVert\vartheta_{S}\rVert^{r}]=Z_{p}\mathbb{E}_{Q_{p}}[\lVert\vartheta_{S}\rVert^{r}]<\infty, E Q S [ w S p ∥ ϑ S ∥ r ] = Z p E Q p [∥ ϑ S ∥ r ] < ∞ ,
which yields (67).
Proof of Theorem 5
Proof. Let the samples ϑ S 1 , … , ϑ S M \vartheta_{S}^{1},\ldots,\vartheta_{S}^{M} ϑ S 1 , … , ϑ S M be generated independently from the initial estimate distribution Q ^ S \widehat{Q}_{S} Q S , and recall from (68) that the finite-sample approximation ϖ ‾ S \overline{\varpi}_{S} ϖ S is the ratio N ‾ M / D ‾ M \overline{N}_{M}/\overline{D}_{M} N M / D M .
The outline is to apply the central limit theorem to the pair of the numerator N ‾ M \overline{N}_{M} N M and the denominator D ‾ M \overline{D}_{M} D M , and to transfer the result to the convergence in distribution of the ratio N ‾ M / D ‾ M \overline{N}_{M}/\overline{D}_{M} N M / D M by the delta method [40 ] . Recall from (67) that, E Q ^ S [ w S 2 ] < ∞ \mathbb{E}_{\widehat{Q}_{S}}[w_{S}^{2}]<\infty E Q S [ w S 2 ] < ∞ and E Q ^ S [ w S 2 ∥ ϑ S ∥ 2 ] < ∞ \mathbb{E}_{\widehat{Q}_{S}}[w_{S}^{2}\lVert\vartheta_{S}\rVert^{2}]<\infty E Q S [ w S 2 ∥ ϑ S ∥ 2 ] < ∞ . Hence the independent and identically distributed random vectors
[ w S ( ϑ S i ) ϑ S i T w S ( ϑ S i ) ] T \left[w_{S}(\vartheta_{S}^{i})\vartheta_{S}^{i\mathsf{T}}\quad w_{S}(\vartheta_{S}^{i})\right]^{\mathsf{T}} [ w S ( ϑ S i ) ϑ S i T w S ( ϑ S i ) ] T
have a finite covariance matrix. By the definition (61) of Z 1 Z_{1} Z 1 and (65), their mean is [ Z 1 m 1 T Z 1 ] T [Z_{1}m_{1}^{\mathsf{T}}\quad Z_{1}]^{\mathsf{T}} [ Z 1 m 1 T Z 1 ] T . The multivariate central limit theorem gives
M ( [ N ‾ M D ‾ M ] − [ Z 1 m 1 Z 1 ] ) → d N ( 0 , Cov Q ^ S [ [ w S ϑ S w S ] ] ) . (96) \sqrt{M}\left(\begin{bmatrix}\overline{N}_{M}\\\overline{D}_{M}\end{bmatrix}-\begin{bmatrix}Z_{1}m_{1}\\Z_{1}\end{bmatrix}\right)\xrightarrow{d}\mathcal{N}\left(0,\operatorname{Cov}_{\widehat{Q}_{S}}\left[\begin{bmatrix}w_{S}\vartheta_{S}\\w_{S}\end{bmatrix}\right]\right). \tag*{(96)} M ( [ N M D M ] − [ Z 1 m 1 Z 1 ] ) d N ( 0 , Cov Q S [ [ w S ϑ S w S ] ] ) . (96)
Applying the delta method to this result, we derive the covariance of the ratio N ‾ M / D ‾ M \overline{N}_M/\overline{D}_M N M / D M .
The ratio map ( N ‾ M , D ‾ M ) ↦ N ‾ M / D ‾ M (\overline{N}_M,\overline{D}_M) \mapsto\overline{N}_M/\overline{D}_M ( N M , D M ) ↦ N M / D M maps the ( m d + 1 ) (md+1) ( m d + 1 ) -dimensional vector formed by the m d md m d -dimensional vector N ‾ M \overline{N}_M N M and the positive scalar D ‾ M \overline{D}_M D M to an m d md m d -dimensional vector. Hence its Jacobian matrix is an m d × ( m d + 1 ) md \times(md+1) m d × ( m d + 1 ) matrix that consists of the partial derivatives with respect to the sample means N ‾ M \overline{N}_M N M and D ‾ M \overline{D}_M D M placed side by side. The partial derivative of the ratio N ‾ M / D ‾ M \overline{N}_M/\overline{D}_M N M / D M with respect to the numerator N ‾ M \overline{N}_M N M is
∂ ∂ N ‾ M [ N ‾ M D ‾ M ] = 1 D ‾ M I m d , (97) \frac{\partial}{\partial\overline{N}_M}\left[\frac{\overline{N}_M}{\overline{D}_M}\right] = \frac{1}{\overline{D}_M}I_{md}, \tag*{(97)} ∂ N M ∂ [ D M N M ] = D M 1 I m d , (97)
and the partial derivative of the ratio N ‾ M / D ‾ M \overline{N}_M/\overline{D}_M N M / D M with respect to the denominator D ‾ M \overline{D}_M D M is
∂ ∂ D ‾ M [ N ‾ M D ‾ M ] = − N ‾ M D ‾ M 2 . (98) \frac{\partial}{\partial\overline{D}_M}\left[\frac{\overline{N}_M}{\overline{D}_M}\right] = -\frac{\overline{N}_M}{\overline{D}_M^2}. \tag*{(98)} ∂ D M ∂ [ D M N M ] = − D M 2 N M . (98)
Placing (97) and (98) side by side and evaluating them at the point ( Z 1 m 1 , Z 1 ) (Z_1m_1,Z_1) ( Z 1 m 1 , Z 1 ) , we obtain the Jacobian matrix
J = [ 1 Z 1 I m d − Z 1 m 1 Z 1 2 ] = 1 Z 1 [ I m d − m 1 ] . (99) \mathcal{J}=\left[\frac{1}{Z_1}I_{md}\quad-\frac{Z_1m_1}{Z_1^2}\right]=\frac{1}{Z_1}\left[I_{md}\quad-m_1\right]. \tag*{(99)} J = [ Z 1 1 I m d − Z 1 2 Z 1 m 1 ] = Z 1 1 [ I m d − m 1 ] . (99)
Since Z 1 > 0 Z_1>0 Z 1 > 0 , the ratio map is differentiable at the point ( Z 1 m 1 , Z 1 ) (Z_1m_1,Z_1) ( Z 1 m 1 , Z 1 ) , and its value at this point is the optimal coefficient, Z 1 m 1 / Z 1 = m 1 = ϖ S ∗ Z_1m_1/Z_1=m_1=\varpi_S^* Z 1 m 1 / Z 1 = m 1 = ϖ S ∗ .
Applying the delta method [40 ] to (96) yields
M ( ϖ S ∗ − ϖ ^ S ∗ ) → d N ( 0 , Cov Q ^ S [ J [ w S ( ϑ S ) ϑ S w S ] ] ) . (100) \sqrt{M}(\varpi_S^*-\widehat{\varpi}_S^*) \xrightarrow{d} \mathcal{N}\left(0,\operatorname{Cov}_{\widehat{Q}_S}\left[\mathcal{J}\left[\frac{w_S(\vartheta_S)\vartheta_S}{w_S}\right]\right]\right). \tag*{(100)} M ( ϖ S ∗ − ϖ S ∗ ) d N ( 0 , Cov Q S [ J [ w S w S ( ϑ S ) ϑ S ] ] ) . (100)
Using (99), we have
J [ w S ( ϑ S ) ϑ S w S ] = w S ( ϑ S ) Z 1 ( ϑ S − m 1 ) . (101) \mathcal{J}\left[\frac{w_S(\vartheta_S)\vartheta_S}{w_S}\right]=\frac{w_S(\vartheta_S)}{Z_1}(\vartheta_S-m_1). \tag*{(101)} J [ w S w S ( ϑ S ) ϑ S ] = Z 1 w S ( ϑ S ) ( ϑ S − m 1 ) . (101)
From the definition (61) of Z 1 Z_1 Z 1 and (65), we see that
E Q ^ S [ w S Z 1 ( ϑ S − m 1 ) ] = 1 Z 1 ( Z 1 m 1 − Z 1 m 1 ) = 0 \mathbb{E}_{\widehat{Q}_S}\left[\frac{w_S}{Z_1}(\vartheta_S-m_1)\right]=\frac{1}{Z_1}(Z_1m_1-Z_1m_1)=0 E Q S [ Z 1 w S ( ϑ S − m 1 ) ] = Z 1 1 ( Z 1 m 1 − Z 1 m 1 ) = 0
holds. Hence the covariance matrix of (101) equals its second moment, that is,
Cov Q ^ S [ w S Z 1 ( ϑ S − m 1 ) ] = 1 Z 1 2 E Q ^ S [ w S 2 ( ϑ S − m 1 ) ( ϑ S − m 1 ) T ] . (102) \operatorname{Cov}_{\widehat{Q}_S}\left[\frac{w_S}{Z_1}(\vartheta_S-m_1)\right]
=\frac{1}{Z_1^2}\mathbb{E}_{\widehat{Q}_S}\left[w_S^2(\vartheta_S-m_1)(\vartheta_S-m_1)^\mathsf{T}\right]. \tag*{(102)} Cov Q S [ Z 1 w S ( ϑ S − m 1 ) ] = Z 1 2 1 E Q S [ w S 2 ( ϑ S − m 1 ) ( ϑ S − m 1 ) T ] . (102)
Expanding the expectation on the right-hand side of (102) and applying the definition (61) of Z 2 Z_2 Z 2 , (65), and (66) yields
E Q ^ S [ w S 2 ( ϑ S − m 1 ) ( ϑ S − m 1 ) T ] = Z 2 [ Λ 2 − 1 + m 2 m 2 T − m 2 m 1 T − m 1 m 2 T + m 1 m 1 T ] = Z 2 [ Λ 2 − 1 + ( m 2 − m 1 ) ( m 2 − m 1 ) T ] . \begin{aligned}
\mathbb{E}_{\widehat{Q}_S}\left[w_S^2(\vartheta_S-m_1)(\vartheta_S-m_1)^\mathsf{T}\right]
&=Z_2\left[\Lambda_2^{-1}+m_2m_2^\mathsf{T}-m_2m_1^\mathsf{T}-m_1m_2^\mathsf{T}+m_1m_1^\mathsf{T}\right]\\
&=Z_2\left[\Lambda_2^{-1}+(m_2-m_1)(m_2-m_1)^\mathsf{T}\right].
\end{aligned} E Q S [ w S 2 ( ϑ S − m 1 ) ( ϑ S − m 1 ) T ] = Z 2 [ Λ 2 − 1 + m 2 m 2 T − m 2 m 1 T − m 1 m 2 T + m 1 m 1 T ] = Z 2 [ Λ 2 − 1 + ( m 2 − m 1 ) ( m 2 − m 1 ) T ] .
Substituting this into (102) and using κ S S = Z 2 / Z 1 2 \kappa_S^S=Z_2/Z_1^2 κ S S = Z 2 / Z 1 2 , defined in (72), the covariance matrix in (100) is reduced to Ξ ( κ S S ) \Xi(\kappa_S^S) Ξ ( κ S S ) of (73).
From (70), we have
E S S M = [ 1 M ∑ i = 1 M w S ( ϑ S i ) ] 2 1 M ∑ i = 1 M w S ( ϑ S i ) 2 . (103) \frac{\mathrm{ESS}}{M}=\frac{\left[\frac{1}{M}\sum_{i=1}^{M}w_S(\vartheta_S^i)\right]^2}{\frac{1}{M}\sum_{i=1}^{M}w_S(\vartheta_S^i)^2}. \tag*{(103)} M ESS = M 1 ∑ i = 1 M w S ( ϑ S i ) 2 [ M 1 ∑ i = 1 M w S ( ϑ S i ) ] 2 . (103)
It follows from (62) that both E Q ^ S [ w S ] = Z 1 \mathbb{E}_{\widehat{Q}_S}[w_S]=Z_1 E Q S [ w S ] = Z 1 and E Q ^ S [ w S 2 ] = Z 2 \mathbb{E}_{\widehat{Q}_S}[w_S^2]=Z_2 E Q S [ w S 2 ] = Z 2 are positive and finite. By the strong law of large numbers, the numerator and the denominator of the right-hand side of (103) converge almost surely to Z 1 2 Z_1^2 Z 1 2 and Z 2 Z_2 Z 2 , respectively. This shows that E S S / M \mathrm{ESS}/M ESS / M converges almost surely to Z 1 2 / Z 2 = 1 / κ S S Z_1^2/Z_2=1/\kappa_S^S Z 1 2 / Z 2 = 1/ κ S S .
The outline is to substitute the closed form (62) of Z p Z_p Z p in Lemma 8 into κ S S = Z 2 / Z 1 2 \kappa_S^S=Z_2/Z_1^2 κ S S = Z 2 / Z 1 2 , defined in (72), and to express the exponent in terms of ν \nu ν , defined in (71). Applying (62) gives
κ S S = Z 2 Z 1 2 = ∣ Σ S ∣ 1 / 2 ∣ Λ 1 ∣ ∣ Λ 2 ∣ 1 / 2 exp ( E ) , (104) \kappa_S^S=\frac{Z_2}{Z_1^2}=\frac{|\Sigma_S|^{1/2}|\Lambda_1|}{|\Lambda_2|^{1/2}}\exp(E), \tag*{(104)} κ S S = Z 1 2 Z 2 = ∣ Λ 2 ∣ 1/2 ∣ Σ S ∣ 1/2 ∣ Λ 1 ∣ exp ( E ) , (104)
where the exponent E E E is
E : = 1 2 ∥ b 2 ∥ Λ 2 − 1 2 − ∥ b 1 ∥ Λ 1 − 1 2 + 1 2 ∥ ϖ ^ S ∥ Σ S − 1 2 . (105) E:=\frac{1}{2}\lVert b_2\rVert_{\Lambda_2^{-1}}^2-\lVert b_1\rVert_{\Lambda_1^{-1}}^2+\frac{1}{2}\lVert\widehat{\varpi}_S\rVert_{\Sigma_S^{-1}}^2. \tag*{(105)} E := 2 1 ∥ b 2 ∥ Λ 2 − 1 2 − ∥ b 1 ∥ Λ 1 − 1 2 + 2 1 ∥ ϖ S ∥ Σ S − 1 2 . (105)
We simplify the coefficient in front of the exponential function in (104). By using (57), the determinant of Λ p \Lambda_p Λ p is ∣ Λ p ∣ = ∣ Σ S ∣ − 1 ∣ I m d + 2 p λ Σ S H S ∣ |\Lambda_p|=|\Sigma_S|^{-1}|I_{md}+\frac{2p}{\lambda}\Sigma_SH_S| ∣ Λ p ∣ = ∣ Σ S ∣ − 1 ∣ I m d + λ 2 p Σ S H S ∣ . Substituting this into (104) yields (76).
We express the exponent (105) in terms of ν \nu ν . Using the definition (59) of m p m_p m p , b 1 b_1 b 1 in (58) satisfies b 1 = − Λ 1 m 1 b_1=-\Lambda_1m_1 b 1 = − Λ 1 m 1 . Furthermore, b 2 b_2 b 2 satisfies
b 2 = 2 b 1 + Σ S − 1 ϖ ^ S . b_2=2b_1+\Sigma_S^{-1}\widehat{\varpi}_S. b 2 = 2 b 1 + Σ S − 1 ϖ S .
Using (33) and (65) with p = 1 p=1 p = 1 , the optimal coefficient satisfies ϖ S ∗ = m 1 \varpi_S^*=m_1 ϖ S ∗ = m 1 . Hence, using (71), ϖ ^ S = m 1 + ν \widehat{\varpi}_S=m_1+\nu ϖ S = m 1 + ν holds. Using this relation and the identity
2 Λ 1 − Σ S − 1 = Λ 2 2\Lambda_1-\Sigma_S^{-1}=\Lambda_2 2 Λ 1 − Σ S − 1 = Λ 2
obtained from (57), we have
b 2 = − 2 Λ 1 m 1 + Σ S − 1 ( m 1 + ν ) = − Λ 2 m 1 + Σ S − 1 ν . (106) b_2=-2\Lambda_1m_1+\Sigma_S^{-1}(m_1+\nu)=-\Lambda_2m_1+\Sigma_S^{-1}\nu. \tag*{(106)} b 2 = − 2 Λ 1 m 1 + Σ S − 1 ( m 1 + ν ) = − Λ 2 m 1 + Σ S − 1 ν . (106)
Substituting b 1 = − Λ 1 m 1 b_1=-\Lambda_1m_1 b 1 = − Λ 1 m 1 , (106), and ϖ ^ S = m 1 + ν \widehat{\varpi}_S=m_1+\nu ϖ S = m 1 + ν into each term of (105) gives
1 2 ∥ b 2 ∥ Λ 2 − 1 2 = 1 2 m 1 T Λ 2 m 1 − m 1 T Σ S − 1 ν + 1 2 ν T Σ S − 1 Λ 2 − 1 Σ S − 1 ν , \frac{1}{2}\lVert b_2\rVert_{\Lambda_2^{-1}}^2=\frac{1}{2}m_1^\mathsf{T}\Lambda_2m_1-m_1^\mathsf{T}\Sigma_S^{-1}\nu+\frac{1}{2}\nu^\mathsf{T}\Sigma_S^{-1}\Lambda_2^{-1}\Sigma_S^{-1}\nu, 2 1 ∥ b 2 ∥ Λ 2 − 1 2 = 2 1 m 1 T Λ 2 m 1 − m 1 T Σ S − 1 ν + 2 1 ν T Σ S − 1 Λ 2 − 1 Σ S − 1 ν ,
∥ b 1 ∥ Λ 1 − 1 2 = m 1 T Λ 1 m 1 , \lVert b_1\rVert_{\Lambda_1^{-1}}^2=m_1^\mathsf{T}\Lambda_1m_1, ∥ b 1 ∥ Λ 1 − 1 2 = m 1 T Λ 1 m 1 ,
1 2 ∥ ϖ ^ S ∥ Σ S − 1 2 = 1 2 m 1 T Σ S − 1 m 1 + m 1 T Σ S − 1 ν + 1 2 ν T Σ S − 1 ν . \frac{1}{2}\lVert\widehat{\varpi}_S\rVert_{\Sigma_S^{-1}}^2=\frac{1}{2}m_1^\mathsf{T}\Sigma_S^{-1}m_1+m_1^\mathsf{T}\Sigma_S^{-1}\nu+\frac{1}{2}\nu^\mathsf{T}\Sigma_S^{-1}\nu. 2 1 ∥ ϖ S ∥ Σ S − 1 2 = 2 1 m 1 T Σ S − 1 m 1 + m 1 T Σ S − 1 ν + 2 1 ν T Σ S − 1 ν .
Therefore, we have the expression
E = 1 2 ν T [ Σ S − 1 + Σ S − 1 Λ 2 − 1 Σ S − 1 ] ν = 1 2 ν T Ψ ν . E=\frac{1}{2}\nu^\mathsf{T}\left[\Sigma_S^{-1}+\Sigma_S^{-1}\Lambda_2^{-1}\Sigma_S^{-1}\right]\nu=\frac{1}{2}\nu^\mathsf{T}\Psi\nu. E = 2 1 ν T [ Σ S − 1 + Σ S − 1 Λ 2 − 1 Σ S − 1 ] ν = 2 1 ν T Ψ ν .
This shows that (74) holds. Moreover, since Σ S − 1 ≻ 0 \Sigma_S^{-1}\succ0 Σ S − 1 ≻ 0 and Σ S − 1 Λ 2 − 1 Σ S − 1 ⪰ 0 \Sigma_S^{-1}\Lambda_2^{-1}\Sigma_S^{-1}\succeq0 Σ S − 1 Λ 2 − 1 Σ S − 1 ⪰ 0 , Ψ \Psi Ψ defined in (75) is positive definite. ■
Details on κ 0 S \kappa_0^S κ 0 S
This section relates κ 0 S \kappa_0^S κ 0 S , defined in (76), to the difference between the covariance matrix Σ S \Sigma_S Σ S of the initial estimate distribution Q ^ S \widehat{Q}_S Q S and the covariance matrix Λ 1 − 1 \Lambda_1^{-1} Λ 1 − 1 of the optimal distribution Q S ∗ Q_S^* Q S ∗ . Let Σ S 1 / 2 \Sigma_S^{1/2} Σ S 1/2 be the symmetric square root of Σ S \Sigma_S Σ S . Since the matrix Σ S 1 / 2 H S Σ S 1 / 2 \Sigma_S^{1/2}H_S\Sigma_S^{1/2} Σ S 1/2 H S Σ S 1/2 is symmetric positive semidefinite, it is diagonalized by an orthogonal matrix O O O as
Σ S 1 / 2 H S Σ S 1 / 2 = O diag ( μ 1 S , … , μ m d S ) O T , \Sigma_S^{1/2}H_S\Sigma_S^{1/2}=O\operatorname{diag}(\mu_1^S,\ldots,\mu_{md}^S)O^\mathsf{T}, Σ S 1/2 H S Σ S 1/2 = O diag ( μ 1 S , … , μ m d S ) O T ,
where μ i S ≥ 0 \mu_i^S \ge0 μ i S ≥ 0 are its eigenvalues. Since Σ S H S = Σ S 1 / 2 ( Σ S 1 / 2 H S Σ S 1 / 2 ) Σ S − 1 / 2 \Sigma_S H_S = \Sigma_S^{1/2}(\Sigma_S^{1/2}H_S\Sigma_S^{1/2})\Sigma_S^{-1/2} Σ S H S = Σ S 1/2 ( Σ S 1/2 H S Σ S 1/2 ) Σ S − 1/2 , these are also the eigenvalues of Σ S 1 / 2 H S Σ S 1 / 2 \Sigma_S^{1/2}H_S\Sigma_S^{1/2} Σ S 1/2 H S Σ S 1/2 .
Using (57) and I m d = O O T I_{md}=OO^{\mathsf T} I m d = O O T , we factorize Λ 1 \Lambda_1 Λ 1 as
Λ 1 = Σ S − 1 / 2 ( I m d + 2 λ Σ S 1 / 2 H S Σ S 1 / 2 ) Σ S − 1 / 2 = Σ S − 1 / 2 O ( I m d + 2 λ diag ( μ 1 S , … , μ m d S ) ) O T Σ S − 1 / 2 . \begin{aligned}
\Lambda_1=\Sigma_S^{-1/2}\left(I_{md}+\frac{2}{\lambda}\Sigma_S^{1/2}H_S\Sigma_S^{1/2}\right)\Sigma_S^{-1/2} \\
&=\Sigma_S^{-1/2}O\left(I_{md}+\frac{2}{\lambda}\operatorname{diag}(\mu_1^S,\ldots,\mu_{md}^S)\right)O^{\mathsf T}\Sigma_S^{-1/2}.
\end{aligned} Λ 1 = Σ S − 1/2 ( I m d + λ 2 Σ S 1/2 H S Σ S 1/2 ) Σ S − 1/2 = Σ S − 1/2 O ( I m d + λ 2 diag ( μ 1 S , … , μ m d S ) ) O T Σ S − 1/2 .
Then, we have Λ 1 − 1 \Lambda_1^{-1} Λ 1 − 1 as
Λ 1 − 1 = Σ S 1 / 2 O ( I m d + 2 λ diag ( μ 1 S , … , μ m d S ) ) − 1 O T Σ S 1 / 2 . \Lambda_1^{-1}=\Sigma_S^{1/2}O\left(I_{md}+\frac{2}{\lambda}\operatorname{diag}(\mu_1^S,\ldots,\mu_{md}^S)\right)^{-1}O^{\mathsf T}\Sigma_S^{1/2}. Λ 1 − 1 = Σ S 1/2 O ( I m d + λ 2 diag ( μ 1 S , … , μ m d S ) ) − 1 O T Σ S 1/2 .
Consider the transformed coefficient O T Σ S − 1 / 2 ϑ S O^{\mathsf T}\Sigma_S^{-1/2}\vartheta_S O T Σ S − 1/2 ϑ S . Its covariance matrices under Q ^ S \widehat{Q}_S Q S and Q S ∗ Q_S^* Q S ∗ are
O T Σ S − 1 / 2 Σ S Σ S − 1 / 2 O = I m d , O^{\mathsf T}\Sigma_S^{-1/2}\Sigma_S\Sigma_S^{-1/2}O=I_{md}, O T Σ S − 1/2 Σ S Σ S − 1/2 O = I m d ,
O T Σ S − 1 / 2 Λ 1 − 1 Σ S − 1 / 2 O = diag ( 1 1 + 2 μ 1 S / λ , … , 1 1 + 2 μ m d S / λ ) , O^{\mathsf T}\Sigma_S^{-1/2}\Lambda_1^{-1}\Sigma_S^{-1/2}O
=\operatorname{diag}\left(\frac{1}{1+2\mu_1^S/\lambda},\ldots,\frac{1}{1+2\mu_{md}^S/\lambda}\right), O T Σ S − 1/2 Λ 1 − 1 Σ S − 1/2 O = diag ( 1 + 2 μ 1 S / λ 1 , … , 1 + 2 μ m d S / λ 1 ) ,
respectively. Thus both covariance matrices are diagonal in these coordinates, and the ratio of the variance under Q ^ S \widehat{Q}_S Q S to that under Q S ∗ Q_S^* Q S ∗ in the i i i -th coordinate is 1 + 2 μ i S / λ ≥ 1 1+2\mu_i^S/\lambda\ge1 1 + 2 μ i S / λ ≥ 1 . Subtracting the two diagonal forms gives
O T Σ S − 1 / 2 ( Σ S − Λ 1 − 1 ) Σ S − 1 / 2 O = diag ( 2 μ 1 S / λ 1 + 2 μ 1 S / λ , … , 2 μ m d S / λ 1 + 2 μ m d S / λ ) . O^{\mathsf T}\Sigma_S^{-1/2}(\Sigma_S-\Lambda_1^{-1})\Sigma_S^{-1/2}O
=\operatorname{diag}\left(\frac{2\mu_1^S/\lambda}{1+2\mu_1^S/\lambda},\ldots,\frac{2\mu_{md}^S/\lambda}{1+2\mu_{md}^S/\lambda}\right). O T Σ S − 1/2 ( Σ S − Λ 1 − 1 ) Σ S − 1/2 O = diag ( 1 + 2 μ 1 S / λ 2 μ 1 S / λ , … , 1 + 2 μ m d S / λ 2 μ m d S / λ ) .
Therefore, Σ S ⪰ Λ 1 − 1 \Sigma_S\succeq\Lambda_1^{-1} Σ S ⪰ Λ 1 − 1 always holds, Σ S ≻ Λ 1 − 1 \Sigma_S\succ\Lambda_1^{-1} Σ S ≻ Λ 1 − 1 holds if and only if μ i S > 0 \mu_i^S>0 μ i S > 0 for all i i i , and Σ S = Λ 1 − 1 \Sigma_S=\Lambda_1^{-1} Σ S = Λ 1 − 1 holds if and only if μ i S = 0 \mu_i^S=0 μ i S = 0 for all i i i .
Since the eigenvalues of I m d + c Σ S H S I_{md}+c\Sigma_SH_S I m d + c Σ S H S are 1 + c μ i S 1+c\mu_i^S 1 + c μ i S for c > 0 c>0 c > 0 , (76) gives κ 0 S = ∏ i = 1 m d ψ ( μ i S ) \kappa_0^S=\prod_{i=1}^{md}\psi(\mu_i^S) κ 0 S = ∏ i = 1 m d ψ ( μ i S ) with the function ψ \psi ψ defined in (82). For μ ≥ 0 \mu\ge0 μ ≥ 0 , ( 1 + 2 μ / λ ) 2 = 1 + 4 μ / λ + 4 μ 2 / λ 2 (1+2\mu/\lambda)^2=1+4\mu/\lambda+4\mu^2/\lambda^2 ( 1 + 2 μ / λ ) 2 = 1 + 4 μ / λ + 4 μ 2 / λ 2 gives ψ ( μ ) ≥ 1 \psi(\mu)\ge1 ψ ( μ ) ≥ 1 , with equality if and only if μ = 0 \mu=0 μ = 0 . Therefore κ 0 S = 1 \kappa_0^S=1 κ 0 S = 1 holds if and only if μ i S = 0 \mu_i^S=0 μ i S = 0 for all i i i , that is, Σ S = Λ 1 − 1 \Sigma_S=\Lambda_1^{-1} Σ S = Λ 1 − 1 . When Σ S ≻ Λ 1 − 1 \Sigma_S\succ\Lambda_1^{-1} Σ S ≻ Λ 1 − 1 , every factor satisfies ψ ( μ i S ) > 1 \psi(\mu_i^S)>1 ψ ( μ i S ) > 1 , and hence κ 0 S > 1 \kappa_0^S>1 κ 0 S > 1 .
Proof of Corollary 2
Proof: The outline is to bound the covariance matrix of the stochastic noise ε M ( k ) \varepsilon_M(k) ε M ( k ) from below by the constant matrix Σ ε / M \Sigma_\varepsilon/M Σ ε / M , defined in (79), and to compare the resulting covariance recursion of the error χ ( k ) \chi(k) χ ( k ) with the Lyapunov recursion, defined in Step 3.
Step 1: Error dynamics. Subtracting (55) from (54) gives
χ ( k + 1 ) = ( A − B K ( S ) ) χ ( k ) + B ε M ( k ) , χ ( 0 ) = 0. (107) \chi(k+1)=(A-BK(S))\chi(k)+B\varepsilon_M(k),\qquad\chi(0)=0. \tag*{(107)} χ ( k + 1 ) = ( A − B K ( S )) χ ( k ) + B ε M ( k ) , χ ( 0 ) = 0. (107)
Since the state x n o m ( k ) x_{\mathrm{nom}}(k) x nom ( k ) of the infinite-sample limit is deterministic, the error χ ( k ) \chi(k) χ ( k ) is determined by the state x ( k ) x(k) x ( k ) . Hence, using (78), in which the mean of ε M ( k ) \varepsilon_M(k) ε M ( k ) for fixed x ( k ) x(k) x ( k ) and ϖ ^ S ( k ) \widehat{\varpi}_S(k) ϖ S ( k ) is zero,
E [ ε M ( k ) ] = 0 , E [ χ ( k ) ε M ( k ) T ] = 0. \mathbb{E}[\varepsilon_M(k)]=0,\qquad\mathbb{E}[\chi(k)\varepsilon_M(k)^{\mathsf T}]=0. E [ ε M ( k )] = 0 , E [ χ ( k ) ε M ( k ) T ] = 0.
Induction on k k k using (107) and χ ( 0 ) = 0 \chi(0)=0 χ ( 0 ) = 0 gives E [ χ ( k ) ] = 0 \mathbb{E}[\chi(k)]=0 E [ χ ( k )] = 0 and
Cov [ χ ( k + 1 ) ] = ( A − B K ( S ) ) Cov [ χ ( k ) ] ( A − B K ( S ) ) T + B Cov [ ε M ( k ) ] B T . (108) \operatorname{Cov}[\chi(k+1)]=(A-BK(S))\operatorname{Cov}[\chi(k)](A-BK(S))^{\mathsf T}+B\operatorname{Cov}[\varepsilon_M(k)]B^{\mathsf T}. \tag*{(108)} Cov [ χ ( k + 1 )] = ( A − B K ( S )) Cov [ χ ( k )] ( A − B K ( S ) ) T + B Cov [ ε M ( k )] B T . (108)
Step 2: Lower bound on the noise covariance. We bound Cov [ ε M ( k ) ] \operatorname{Cov}[\varepsilon_M(k)] Cov [ ε M ( k )] from below. Using (74) and Ψ ≻ 0 \Psi\succ0 Ψ ≻ 0 , we have κ S ≥ κ 0 S \kappa^S\ge\kappa_0^S κ S ≥ κ 0 S . Since ( m 2 − m 1 ) ( m 2 − m 1 ) T ⪰ 0 (m_2-m_1)(m_2-m_1)^{\mathsf T}\succeq0 ( m 2 − m 1 ) ( m 2 − m 1 ) T ⪰ 0 , using (73) gives
Ξ ( κ S ) ⪰ κ S Λ 2 − 1 ⪰ κ 0 S Λ 2 − 1 . \Xi(\kappa^S)\succeq\kappa^S\Lambda_2^{-1}\succeq\kappa_0^S\Lambda_2^{-1}. Ξ ( κ S ) ⪰ κ S Λ 2 − 1 ⪰ κ 0 S Λ 2 − 1 .
Hence the covariance matrix P S ( 0 ) Ξ ( κ S ) P S ( 0 ) T / M P_S(0)\Xi(\kappa^S)P_S(0)^{\mathsf T}/M P S ( 0 ) Ξ ( κ S ) P S ( 0 ) T / M of ε M ( k ) \varepsilon_M(k) ε M ( k ) for fixed x ( k ) x(k) x ( k ) and ϖ ^ S ( k ) \widehat{\varpi}_S(k) ϖ S ( k ) is no smaller than Σ ε / M \Sigma_\varepsilon/M Σ ε / M for any x ( k ) x(k) x ( k ) and ϖ ^ S ( k ) \widehat{\varpi}_S(k) ϖ S ( k ) . Since the mean for fixed x ( k ) x(k) x ( k ) and ϖ ^ S ( k ) \widehat{\varpi}_S(k) ϖ S ( k ) is zero, Cov [ ε M ( k ) ] \operatorname{Cov}[\varepsilon_M(k)] Cov [ ε M ( k )] equals the expectation of this covariance matrix over x ( k ) x(k) x ( k ) and ϖ ^ S ( k ) \widehat{\varpi}_S(k) ϖ S ( k ) , and therefore
Cov [ ε M ( k ) ] ⪰ Σ ε M . \operatorname{Cov}[\varepsilon_M(k)]\succeq\frac{\Sigma_\varepsilon}{M}. Cov [ ε M ( k )] ⪰ M Σ ε .
Step 3: Time-wise lower bound. Let Υ ( k ) \Upsilon(k) Υ ( k ) be given by
Υ ( k + 1 ) = ( A − B K ( S ) ) Υ ( k ) ( A − B K ( S ) ) T + B Σ ε B T , (109) \Upsilon(k+1)=(A-BK(S))\Upsilon(k)(A-BK(S))^{\mathsf T}+B\Sigma_\varepsilon B^{\mathsf T}, \tag*{(109)} Υ ( k + 1 ) = ( A − B K ( S )) Υ ( k ) ( A − B K ( S ) ) T + B Σ ε B T , (109)
where Υ ( 0 ) = 0 \Upsilon(0)=0 Υ ( 0 ) = 0 . For symmetric matrices X ⪰ Y X\succeq Y X ⪰ Y , ( A − B K ( S ) ) X ( A − B K ( S ) ) T ⪰ ( A − B K ( S ) ) Y ( A − B K ( S ) ) T (A-BK(S))X(A-BK(S))^{\mathsf T}\succeq(A-BK(S))Y(A-BK(S))^{\mathsf T} ( A − B K ( S )) X ( A − B K ( S ) ) T ⪰ ( A − B K ( S )) Y ( A − B K ( S ) ) T holds. Hence induction on k k k using (108), (109), and Cov [ χ ( 0 ) ] = Υ ( 0 ) = 0 \operatorname{Cov}[\chi(0)]=\Upsilon(0)=0 Cov [ χ ( 0 )] = Υ ( 0 ) = 0 gives Cov [ χ ( k ) ] ⪰ Υ ( k ) / M \operatorname{Cov}[\chi(k)]\succeq\Upsilon(k)/M Cov [ χ ( k )] ⪰ Υ ( k ) / M for all k ≥ 0 k\ge0 k ≥ 0 . Since E [ ∥ χ ( k ) ∥ 2 ] = tr Cov [ χ ( k ) ] ≥ tr Υ ( k ) / M \mathbb{E}[\|\chi(k)\|^2]=\operatorname{tr}\operatorname{Cov}[\chi(k)]\ge\operatorname{tr}\Upsilon(k)/M E [ ∥ χ ( k ) ∥ 2 ] = tr Cov [ χ ( k )] ≥ tr Υ ( k ) / M .
Step 4: Limit. Solving (109) gives
Υ ( k ) = ∑ j = 0 k − 1 ( A − B K ( S ) ) j B Σ ε B T ( ( A − B K ( S ) ) j ) T . \Upsilon(k)=\sum_{j=0}^{k-1}(A-BK(S))^jB\Sigma_\varepsilon B^{\mathsf T}\left((A-BK(S))^j\right)^{\mathsf T}. Υ ( k ) = j = 0 ∑ k − 1 ( A − B K ( S ) ) j B Σ ε B T ( ( A − B K ( S ) ) j ) T .
Under the stability condition (56), this series converges as k → ∞ k\to\infty k → ∞ , and its limit is the unique solution Υ \Upsilon Υ of (80) [41 ] . If E [ ∥ χ ( k ) ∥ 2 ] ≤ χ 0 2 \mathbb{E}[\|\chi(k)\|^2]\le\chi_0^2 E [ ∥ χ ( k ) ∥ 2 ] ≤ χ 0 2 holds for all k ≥ 0 k\ge0 k ≥ 0 , then Step 3 gives tr Υ ( k ) ≤ M χ 0 2 \operatorname{tr}\Upsilon(k)\le M\chi_0^2 tr Υ ( k ) ≤ M χ 0 2 for all $k\ge 0, and letting k → ∞ k\to\infty k → ∞ yields (81). ■
Proof of Theorem 6
Proof: 1) The outline is to rewrite the two determinants in (76) as products of the eigenvalues μ i ( N , S ) \mu_i(N,S) μ i ( N , S ) . Since
Σ S − 1 / 2 ( Σ S H S ) Σ S 1 / 2 = Σ S 1 / 2 H S Σ S 1 / 2 , \Sigma_S^{-1/2}(\Sigma_SH_S)\Sigma_S^{1/2}=\Sigma_S^{1/2}H_S\Sigma_S^{1/2}, Σ S − 1/2 ( Σ S H S ) Σ S 1/2 = Σ S 1/2 H S Σ S 1/2 ,
the matrix Σ S H S \Sigma_SH_S Σ S H S is similar to Σ S 1 / 2 H S Σ S 1 / 2 \Sigma_S^{1/2}H_S\Sigma_S^{1/2} Σ S 1/2 H S Σ S 1/2 and has the eigenvalues μ i ( N , S ) \mu_i(N,S) μ i ( N , S ) . Hence, for a constant c > 0 c>0 c > 0 , the eigenvalues of I m d + c Σ S H S I_{md}+c\Sigma_SH_S I m d + c Σ S H S are 1 + c μ i ( N , S ) 1+c\mu_i(N,S) 1 + c μ i ( N , S ) , and
∣ I m d + c Σ S H S ∣ = ∏ i = 1 m d ( 1 + c μ i ( N , S ) ) . \left|I_{md}+c\Sigma_SH_S\right|=\prod_{i=1}^{md}(1+c\mu_i(N,S)). ∣ I m d + c Σ S H S ∣ = i = 1 ∏ m d ( 1 + c μ i ( N , S )) .
Applying this expression with c = 2 / λ c=2/\lambda c = 2/ λ and c = 4 / λ c=4/\lambda c = 4/ λ to the numerator and the denominator of (76), respectively, yields (83).
The outline is to regard the pair ( N , S ) (N,S) ( N , S ) as a selection from the T T T candidate basis functions, to compare the eigenvalues of the two pairs by the Courant–Fischer theorem, and to apply the monotonicity of ψ \psi ψ to (83) .
Step 1: Embedding into the full basis. Let L T ( k ) L_T(k) L T ( k ) denote L ( k ) L(k) L ( k ) with N = T N=T N = T . Since the basis function l i ( k ) l_i(k) l i ( k ) , defined in (18) , does not depend on N N N , Assumption 3 gives L ( k ) = [ I N 0 ] L T ( k ) L(k) = [I_N\ 0]L_T(k) L ( k ) = [ I N 0 ] L T ( k ) . Let
S ˉ : = ( I m ⊗ [ I N 0 ] ) S ∈ { 0 , 1 } m T × m d . \bar{S} := \left(I_m \otimes\begin{bmatrix} I_N \\ 0 \end{bmatrix}\right)S \in\{0,1\}^{m_T \times m_d}. S ˉ := ( I m ⊗ [ I N 0 ] ) S ∈ { 0 , 1 } m T × m d .
whose columns are distinct unit vectors. Using the mixed-product property of the Kronecker product, P S ( k ) P_S(k) P S ( k ) , defined in (23) , satisfies
P S ( k ) = ( I m ⊗ L T ( k ) ⊤ ) S ˉ . (110) P_S(k) = (I_m \otimes L_T(k)^\top)\bar{S}. \tag*{(110)} P S ( k ) = ( I m ⊗ L T ( k ) ⊤ ) S ˉ . (110)
Step 2: Relation between the matrices. Let H I H_I H I and Σ I \Sigma_I Σ I denote H S H_S H S and Σ S \Sigma_S Σ S with N = T N=T N = T and S = I m T S=I_{m_T} S = I m T . Using (44) and (23) , we have B ˉ k S = ∑ j = 0 k − 1 A k − 1 − j B P S ( j ) \bar{B}_{kS} = \sum_{j=0}^{k-1} A^{k-1-j}B P_S(j) B ˉ k S = ∑ j = 0 k − 1 A k − 1 − j B P S ( j ) . Substituting (110) into this expression, (48), (46), and (35) yields
H S = S ˉ ⊤ H I S ˉ , Σ S − 1 = S ˉ ⊤ Σ I − 1 S ˉ . (111) H_S = \bar{S}^{\top}H_I\bar{S}, \qquad\Sigma_S^{-1} = \bar{S}^{\top}\Sigma_I^{-1}\bar{S}. \tag*{(111)} H S = S ˉ ⊤ H I S ˉ , Σ S − 1 = S ˉ ⊤ Σ I − 1 S ˉ . (111)
Step 3: Max-min representation of the eigenvalues. Applying the Courant–Fischer theorem [42 ] to Σ S 1 / 2 H S Σ S 1 / 2 \Sigma_S^{1/2}H_S\Sigma_S^{1/2} Σ S 1/2 H S Σ S 1/2 and changing the variables by ϑ S = Σ S 1 / 2 y \vartheta_S = \Sigma_S^{1/2}y ϑ S = Σ S 1/2 y yield
μ i ( N , S ) = max dim X = i min ϑ S ∈ X ∖ { 0 } ϑ S ⊤ H S ϑ S ϑ S ⊤ Σ S − 1 ϑ S . \mu_i(N,S) = \max_{\substack{\dim\mathcal{X}=i}} \min_{\vartheta_S \in\mathcal{X}\setminus\{0\}} \frac{\vartheta_S^\top H_S\vartheta_S}{\vartheta_S^\top\Sigma_S^{-1}\vartheta_S}. μ i ( N , S ) = d i m X = i max ϑ S ∈ X ∖ { 0 } min ϑ S ⊤ Σ S − 1 ϑ S ϑ S ⊤ H S ϑ S .
where X \mathcal{X} X ranges over the i i i -dimensional subspaces of R m d \mathbb{R}^{m_d} R m d . For ϑ ∈ R m T ∖ { 0 } \vartheta\in\mathbb{R}^{m_T}\setminus\{0\} ϑ ∈ R m T ∖ { 0 } , let
R ( ϑ ) : = ϑ ⊤ H I ϑ ϑ ⊤ Σ I − 1 ϑ . R(\vartheta) := \frac{\vartheta^\top H_I\vartheta}{\vartheta^\top\Sigma_I^{-1}\vartheta}. R ( ϑ ) := ϑ ⊤ Σ I − 1 ϑ ϑ ⊤ H I ϑ .
By (111), the quotient above equals R ( S ˉ ϑ S ) R(\bar{S}\vartheta_S) R ( S ˉ ϑ S ) . Since S ˉ \bar{S} S ˉ is of full column rank, the map X ↦ S ˉ X \mathcal{X} \mapsto\bar{S}\mathcal{X} X ↦ S ˉ X is a one-to-one correspondence between the i i i -dimensional subspaces of R m d \mathbb{R}^{m_d} R m d and those contained in Im ( S ˉ ) \operatorname{Im}(\bar{S}) Im ( S ˉ ) . Hence
μ i ( N , S ) = max W ⊂ Im ( S ˉ ) dim W = i min ϑ ∈ W ∖ { 0 } R ( ϑ ) , \mu_i(N,S) = \max_{\substack{\mathcal{W}\subset\operatorname{Im}(\bar{S})\\ \dim\mathcal{W}=i}} \min_{\vartheta\in\mathcal{W}\setminus\{0\}} R(\vartheta), μ i ( N , S ) = W ⊂ Im ( S ˉ ) d i m W = i max ϑ ∈ W ∖ { 0 } min R ( ϑ ) ,
μ i ( T , I m T ) = max W ⊂ R m T dim W = i min ϑ ∈ W ∖ { 0 } R ( ϑ ) . \mu_i(T,I_{m_T}) = \max_{\substack{\mathcal{W}\subset\mathbb{R}^{m_T}\\ \dim\mathcal{W}=i}} \min_{\vartheta\in\mathcal{W}\setminus\{0\}} R(\vartheta). μ i ( T , I m T ) = W ⊂ R m T d i m W = i max ϑ ∈ W ∖ { 0 } min R ( ϑ ) .
The range of the first maximization is included in that of the second, and therefore
μ i ( N , S ) ≤ μ i ( T , I m T ) , i ∈ { 1 , … , m d } . \mu_i(N,S) \le\mu_i(T,I_{m_T}), \qquad i \in\{1,\ldots,m_d\}. μ i ( N , S ) ≤ μ i ( T , I m T ) , i ∈ { 1 , … , m d } .
Step 4: Properties of ψ \psi ψ . For μ ≥ 0 \mu\ge0 μ ≥ 0 , the inequality ( 1 + 2 μ / λ ) 2 ≥ 1 + 4 μ / λ (1+2\mu/\lambda)^2 \ge1+4\mu/\lambda ( 1 + 2 μ / λ ) 2 ≥ 1 + 4 μ / λ gives ψ ( μ ) ≥ 1 \psi(\mu) \ge1 ψ ( μ ) ≥ 1 . In addition, for μ ≥ 0 \mu\ge0 μ ≥ 0 ,
d d μ ln ψ ( μ ) = 2 λ + 2 μ − 2 λ + 4 μ ≥ 0 , \frac{d}{d\mu}\ln\psi(\mu) = \frac{2}{\lambda+2\mu} - \frac{2}{\lambda+4\mu} \ge0, d μ d ln ψ ( μ ) = λ + 2 μ 2 − λ + 4 μ 2 ≥ 0 ,
and hence ψ \psi ψ is monotonically nondecreasing on μ ≥ 0 \mu\ge0 μ ≥ 0 .
Step 5: Comparison. Since d ≤ N ≤ T d \le N \le T d ≤ N ≤ T , the dimensions satisfy m d ≤ m T m_d \le m_T m d ≤ m T . Using (83) , Step 3, and Step 4, we obtain
κ 0 ( N , S ) = ∏ i = 1 m d ψ ( μ i ( N , S ) ) ≤ ∏ i = 1 m d ψ ( μ i ( T , I m T ) ) ≤ ∏ i = 1 m T ψ ( μ i ( T , I m T ) ) = κ 0 ( T , I m T ) , \begin{aligned}
\kappa_0(N,S) = \prod_{i=1}^{m_d}\psi(\mu_i(N,S)) \le\prod_{i=1}^{m_d}\psi(\mu_i(T,I_{m_T})) \\
&\le\prod_{i=1}^{m_T}\psi(\mu_i(T,I_{m_T})) = \kappa_0(T,I_{m_T}),
\end{aligned} κ 0 ( N , S ) = i = 1 ∏ m d ψ ( μ i ( N , S )) ≤ i = 1 ∏ m d ψ ( μ i ( T , I m T )) ≤ i = 1 ∏ m T ψ ( μ i ( T , I m T )) = κ 0 ( T , I m T ) ,
where the first inequality follows from the monotonicity of ψ \psi ψ and the second from ψ ≥ 1 \psi\ge1 ψ ≥ 1 . ■