This paper deals with a homoskedastic errors-in-variables linear regression model and properties of the total least squares (TLS) estimator. We partly revise the consistency results for the TLS estimator previously obtained by the author [18]. We present complete and comprehensive proofs of consistency theorems. A theoretical foundation for construction of the TLS estimator and its relation to the generalized eigenvalue problem is explained. Particularly, the uniqueness of the estimate is proved. The Frobenius norm in the definition of the estimator can be substituted by the spectral norm, or by any other unitarily invariant norm; then the consistency results are still valid.
Errors in variablesfunctional modellinear regressionmeasurement error modelmultivariate regressiontotal least squaresstrong consistency62J0562H12Introduction
We consider a functional linear error-in-variables model. Let {ai0,i≥1} be a sequence of unobserved nonrandom n-dimensional vectors. The elements of the vectors are true explanatory variables or (in other terminology) true regressors. We observe m n-dimensional random vectors a1,…,am and m d-dimensional random vectors b1,…,bm. They are thought to be true vectors ai0 and X0⊤ai0, respectively, plus additive errors:
bi=X0⊤ai0+b˜i,ai=ai0+a˜i,
where a˜i and b˜i are random measurement errors in the regressor and in the response. A nonrandom matrix X0 is estimated based on observations ai, bi, i=1,…,m.
This problem is related to finding an approximate solution to incompatible linear equations (“overdetermined” linear equation, because the number of equations exceeds the number of variables)
AX≈B,
where A=[a1,…,am]⊤ is an m×n matrix and B=[b1,…,bm]⊤ is an m×d matrix. Here X is an unknown n×d matrix.
In the linear error-in-variables regression model (1), the Total Least Squares (TLS) estimator in widely used. It is a multivariate equivalent to the orthogonal regression estimator. We are looking for conditions that provide consistency or strong consistency of the estimator. It is assumed (for granted) that the measurement errors c˜i=(a˜ib˜i), i=1,2,…, are independent and have the same covariance matrix Σ. It may be singular. In particular, some of regressors may be observed without errors. (If the matrix Σ is nonsingular, the proofs can be simplified.) An intercept can be introduced into (1) by augmenting the model and inserting a constant error-free regressor.
Sufficient conditions for consistency of the estimator are presented in Gleser [5], Gallo [4], Kukush and Van Huffel [10]. In [18], the consistency results are obtained under less restrictive conditions than in [10]. In particular, there is no requirement that
λmin2(A0⊤A0)λmax(A0⊤A0)→∞asm→∞,
where A0=[a10,…,am0]⊤ is the matrix A without measurement errors. Hereafter, λmin and λmax denotes the minimum and maximum eigenvalues of a matrix if all the eigenvalues are real numbers. The matrix A0⊤A0 is symmetric (and positive semidefinite). Hence, its eigenvalues are real (and nonnegative).
The model where some variables are explanatory and the other are response is called explicit. The alternative is the implicit model, where all the variables are treated equally. In the implicit model, the n-dimensional linear subspace in Rn+d is fitted to an observed set of points. Some n-dimensional subspaces can be represented in a form {(a,b)∈Rn+d:b=X⊤a} for some n×d matrix X; such subspaces are called generic. The other subspaces are called non-generic. The true points lie on a generic subspace {(a,b):b=X0⊤a}. A consistently estimated subspace must be generic with high probability. We state our results for the explicit model, but use the ideas of the implicit model in the definition of the estimator, as well as in proofs.
We allow errors in different variables to correlate. Our problem is a minor generalization of the mixed LS-TLS problem, which is studied in [20, Section 3.5]. In the latter problem, some explanatory variables are observed without errors; the other explanatory variables and all the response variables are observed with errors. The errors have the same variance and are uncorrelated. The basic LS model (where the explanatory variables are error-free, and the response variables are error-ridden) and the basic TLS model (where all the variables are observed with error, and the errors are uncorrelated) are marginal cases of the mixed LS-TLS problem. By a linear transformation of variables our model can be transformed into either a mixed LS-TLS or basic LS or basic TLS problem. (We do not handle the case where there are more error-free variables than explanatory variables.) Such a transformation does not always preserve the sets of generic and non-generic subspaces. The mixed LS-TLS problem can be transformed into the basic TLS problem as it is shown in [6].
The Weighted TLS and Structured TLS estimators are generalizations of the TLS estimator for the cases where the error covariance matrices do not coincide for different observations or where the errors for different observations are dependent; more precisely, the independence condition is replaced with the condition on the “structure of the errors”. The consistency of these estimators is proved in Kukush and Van Huffel [10] and Kukush et al. [9]. Relaxing conditions for consistency of the Weighted TLS and Structured TLS estimators is an interesting topic for a future research. For generalizations of the TLS problem, see the monograph [13] and the review [12].
In the present paper, for a multivariate regression model with multiple response variables we consider two versions of the TLS estimator. In these estimators, different norms of the weighted residual matrix are minimized. (These estimators coincide for the univariate regression model.) The common way to construct the estimator is to minimize the Frobenius norm. The estimator that minimizes the Frobenius norm also minimizes the spectral norm. Any estimator that minimizes the spectral norm is consistent under conditions of our consistency theorems (see Theorems 3.5–3.7 in Section 3). We also provide a sufficient condition for uniqueness of the estimator that minimizes the Frobenius norm.
In this paper, for the results on consistency of the TLS estimator which are stated in paper [18], we provide complete and comprehensive proofs and present all necessary auxiliary and complementary results. For convenience of the reader we first present the sketch of proof. Detailed proofs are postponed to the appendix. Moreover, the paper contains new results on the relation between the TLS estimator and the generalized eigenvalue problem.
The structure of the paper is as follows. In Section 2 we introduce the model and define the TLS estimator. The consistency theorems for different moment conditions on the errors and for different senses of consistency are stated in Section 3, and their proofs are sketched in Section 5. Section 4 states the existence and uniqueness of the TLS estimator. Auxiliary theoretical constructions and theorems are presented in Section 6. Section 7 explains the relationship between the TLS estimator and the generalized eigenvalue problem. The results in Section 7 are used in construction of the TLS estimator and in the proof of its uniqueness. Detailed proofs are moved to the appendix (Section 8).
Notations
At first, we list the general notation. For v=(xk)k=1n being a vector, ‖v‖=∑k=1nxk2 is the 2-norm of v.
For M=(xi,j)i=1mj=1n being an m×n matrix, ‖M‖=maxv≠0‖Mv‖‖v‖=σmax(M) is the spectral norm of M; ‖M‖F=∑i=1m∑j=1nxi,j2 is the Frobenius norm of M; σmax(M)=σ1(M)≥σ2(M)≥⋯≥σmin(m,n)(M)≥0 are the singular values of M, arranged in descending order; span⟨M⟩ is the column space of M; rkM is the rank of M. For a square n×n matrix M, defM=n−rkM is rank deficiency of M; trM=∑i=1nxi,i is the trace of M; χM(λ)=det(M−λI) is the characteristic polynomial of M. If M is an n×n matrix with real eigenvalues (e.g., if M is Hermitian or if M admits a decomposition M=AB, where A and B are Hermitian matrices, and either A or B is positive semidefinite), λmin(M)=λ1(M)≤λ2(M)≤⋯≤λn(M)=λmax(M) are eigenvalues of M arranged in ascending order.
For V1 and V2 being linear subspaces of Rn of equal dimension dimV1=dimV2, ‖sin∠(V1,V2)‖=‖PV1−PV2‖=‖PV1(I−PV2)‖ is the greatest sine of the canonical angles between V1 and V2. See Section 6.2 for more general definitions.
Now, list the model-specific notations. The notations (except for the matrix Σ) come from [9]. The notations are listed here only for reference; they are introduced elsewhere in this paper – in Sections 1 and 2.
n is the number of regressors, i.e., the number of explanatory variables for each observation; d is the number of response variables for each observation; m is the number of observations, i.e., the sample size.
is the matrix of true variables. It is an m×(n+d) nonrandom matrix. The left-hand block A0 of size m×n consists of true explanatory variables, and the right-hand block B0 of size m×d consists of true response variables.
is the matrix of errors. It is an m×(n+d) random matrix.
is the matrix of observations. It is an m×(n+d) random matrix.
Σ
is a covariance matrix of errors for one observation. For every i, it is assumed that Ec˜i=0 and Ec˜ic˜i⊤=Σ. The matrix Σ is symmetric, positive semidefinite, nonrandom, and of size (n+d)×(n+d). It is assumed known when we construct the TLS estimator.
X0
is the matrix of true regression parameters. It is a nonrandom n×d matrix and is a parameter of interest.
Xext0=X0−I
is an augmented matrix of regression coefficients. It is a nonrandom (n+d)×d matrix.
Xˆ
is the TLS estimator of the matrix X0.
Xˆext
is a matrix whose column space span⟨Xˆext⟩ is considered an estimator of the subspace span⟨Xext0⟩. The matrix Xˆext is of size (n+d)×d. For fixed m and Σ, Xˆext is a Borel measurable function of the matrix C.
While in consistency theorems m tends to ∞, all matrices in this list except Σ, X0 and Xext0 silently depend on m. For example, in equations “limm→∞λmin(A0⊤A0)=+∞” and “Xˆ→X0 almost surely” the matrices A0 and Xˆ depend on m.
The model and the estimatorStatistical model
It is assumed that the matrices A0 and B0 satisfy the relation
A0m×n·X0n×d=B0m×d.
They are observed with measurement errors A˜ and B˜, that is
A=A0+A˜,B=B0+B˜.
The matrix X0 is a parameter of interest.
Rewrite the relation in an implicit form. Let the m×(n+d) block matrices C0,C˜,C∈Rm×(n+d) be constructed by binding “respective versions” of matrices A and B:
C0=[A0B0],C˜=[A˜B˜],C=[AB].
Denote Xext0=(X0−Id). Then
C0m×(n+d)·Xext0(n+d)×d=0m×d.
The entries of the matrix C˜ are denoted δij; the rows are c˜i:
C˜=(δij)i=1mj=1n+d,c˜i=(δij)j=1n+d.
Throughout the paper the following three conditions are assumed to be true: The rowsc˜iof the matrixC˜are mutually independent random vectors.EC˜=0, andEc˜ic˜i⊤:=(Eδijδik)i=1,k=1n+dn+d=Σfor alli=1,…,m.rk(ΣXext0)=d.(simple univariate linear regression with intercept).
For i=1,…,mxi=ξi+δi;yi=β0+β1ξi+εi,
where the measurement errors δi, εi, i=1,…,m, – all the 2m variables – are uncorrelated, Eδi=0, Eδi2=σδ2, Eεi=0, and Eεi2=σε2. A sequence {(xi,yi),i=1,…,m} is observed. The parameters β0 and β1 are to be estimated.
This example is taken from [1, Section 1.1]. But the notation in Example 2.1 and elsewhere in the paper is different. Our notation is ai0=(1,ξi)⊤, bi0=ηi, ai=(1,xi)⊤, bi=yi, δi,1=0, δi,2=δi, δi,3=εi, Σ=diag(0,σδ2,σε2), and X0=(β0,β1)⊤.
For some matrices Σ, (6) is satisfied for any n×d matrix X0. If the matrix Σ in nonsingular, then condition (6) is satisfied. If the errors in the explanatory variables and in the response are uncorrelated, i.e., if the matrix Σ has a block-diagonal form
Σ=Σaa00Σbb
(where Σaa=Ea˜ia˜i⊤ and Σbb=Eb˜ib˜i⊤) with nonsingular matrix Σbb, then condition (6) is satisfied. For example, in the basic mixed LS-TLS problem Σ is diagonal, Σbb is nonsingular, and so (6) holds true. If the null-space of the matrix Σ (which equals span⟨Σ⟩⊥ because Σ is symmetric) lies inside the subspace spanned by the first n (of n+d) standard basis vectors, then condition (6) is also satisfied. On the other hand, if rkΣ<d, then condition (6) is not satisfied.
Total least squares (TLS) estimator
First, find the m×(n+d) matrix Δ for which the constrained minimum is attained
‖Δ(Σ1/2)†‖F→min;Δ(I−PΣ)=0;rk(C−Δ)≤n.
Hereafter Σ† is the Moore–Penrose pseudoinverse matrix of the matrix Σ, PΣ is an orthogonal projector onto the column space of Σ, PΣ=ΣΣ†.
Now, show that the minimum in (7) is attained. The constraint rk(C−Δ)≤n is satisfied if and only if all the minors of C−Δ of order n+1 vanish. Thus the set of all Δ that satisfy the constraints (the constraint set) is defined by m!(n+d)!(n+1)!2(m−n−1)!(d−1)!+1 algebraic equations; and so it is closed. The constraint set is nonempty almost surely because it contains C˜. The functional ‖ΔΣ†‖F is a pseudonorm on Rm×(n+d), but it is a norm on the linear subspace {Δ:Δ(I−Σ†)=0}, where it induces a natural subspace topology. The constraint set is closed on the subspace (with the norm), and whenever it is nonempty (i.e., almost surely), it has a minimal-norm element.
Notice that under condition (6) the constrain set is non-empty always and not just almost surely. This follows from Proposition 7.9.
For the matrix Δ that is a solution to minimization problem (7), consider the rowspace span⟨(C−Δ)⊤⟩ of the matrix C−Δ. Its dimension does not exceed n. Its orthogonal basis can be completed to the orthogonal basis in Rn+d, and the complement consists of n+d−rk(C−Δ)≥d vectors. Choose d vectors from the complement, which are linearly independent, and bind them (as column-vectors) into (n+d)×d matrix Xˆext. The matrix Xˆext satisfies the equation
(C−Δ)Xˆext=0.
If the lower d×d block of the matrix Xˆext is a nonsingular matrix, by linear transformation of columns (i.e., by right-multiplying by some nonsingular matrix) the matrix Xˆext can be transformed to the form
Xˆ−I,
where I is d×d identity matrix. The matrix Xˆ satisfies the equation
(C−Δ)Xˆ−I=0.
(Otherwise, if the lower block of the matrix Xˆext is singular, then our estimation fails. Note that whether the lower block of the matrix Xˆext is singular might depend not only on the observations C, but also on the choice of the matrix Δ where the minimum in (7) in attained and the d vectors that make matrix Xˆext. We will show that the lower block of the matrix Xˆext is nonsingular with high probability regardless of the choice of Δ and Xˆext.)
Columns of the matrix Xˆext should span the eigenspace (generalized invariant space) of the matrix pencil ⟨C⊤C,Σ⟩ which corresponds to the d smallest generalized eigenvalues. That the columns of the matrix Xˆext span the generalized invariant space corresponding to finite generalized eigenvalues is written in the matrix notation as follows:
∃M∈Rd×d:C⊤CXˆext=ΣXˆextM.
Possible problems that may arise in the course of solving the minimization problem (7) are discussed in [18]. We should mention that our two-step definition (7) & (9) of the TLS estimator is slightly different from the conventional definition in [20, Sections 2.3.2 and 3.2] or in [10]. In these papers, the problem from which the estimator Xˆ is found is equivalent to the following:
‖Δ(Σ1/2)†‖F→min;Δ(I−PΣ)=0;(C−Δ)Xˆ−I=0,
where the optimization is performed for Δ and Xˆ that satisfy the constraints in (10). If our estimation defined with (7) and (9) succeeds, then the minimum values in (7) and (10) coincide, and the minimum in (10) is attained for (Δ,Xˆ) that is the solution to (7) & (9). Conversely, if our estimation succeeds for at least one choice of Δ and Xˆext, then all the solutions to (10) can be obtained with different choices of Δ and Xˆext. However, strange things may happen if our estimation always fails.
Besides (7), consider the optimization problem
λmax(ΔΣ†Δ⊤)→min;Δ(I−PΣ)=0;rk(C−Δ)≤n.
It will be shown that every Δ that minimizes (7) also minimizes (11).
We can construct the optimization problem that generalizes both (7) and (11). Let ‖M‖U be a unitarily invariant norm on m×(n+d) matrices. Consider the optimization problem
‖Δ(Σ1/2)†‖U→min;Δ(I−PΣ)=0;rk(C−Δ)≤n.
Then every Δ that minimizes (7) also minimizes (12), and every Δ that minimizes (12) also minimizes (11). If ‖M‖U is the Frobenius norm, then optimization problems (7) and (12) coincide, and if ‖M‖U is the spectral norm, then optimization problems (11) and (12) coincide.
A solution to problem (7) or (11) does not change if the matrix Σ is multiplied by a positive scalar factor. Thus, instead of assuming that the matrix Σ is known completely, we can assume that Σ is known up to a scalar factor.
Known consistency results
In this section we briefly revise known consistency results. One of conditions for the consistency of the TLS estimator is the convergence of 1mA0⊤A0 to a nonsingular matrix. It is required, for example, in [5]. The condition is relaxed in the paper by Gallo [4].
Letd=1,m−1/2λmin(A0⊤A0)→∞asm→∞,λmin2(A0⊤A0)λmax(A0⊤A0)→∞asm→∞,and the measurement errorsc˜iare identically distributed, with finite fourth momentE‖c˜i‖4<∞. ThenXˆ⟶PX0,m→∞.
The theorem can be generalized for the multivariate regression. The condition that the errors on different observations have the same distribution can be dropped. Instead, Kukush and Van Huffel [10] assume that the fourth moments of the error distributions are bounded.
(Kukush and Van Huffel [<xref ref-type="bibr" rid="j_vmsta104_ref_010">10</xref>], Theorem 4a).
(Kukush and Van Huffel [<xref ref-type="bibr" rid="j_vmsta104_ref_010">10</xref>], Theorem 4b).
Let for somer≥2andm0≥1,supi≥1j=1,…,n+dE|δij|2r<∞,∑m=m0∞(mλmin(A0⊤A0))r<∞,∑m=m0∞(λmax(A0⊤A0)λmin2(A0⊤A0))r<∞.ThenXˆ→X0asm→∞, almost surely.
In the following consistency theorem the moment condition imposed on the errors is relaxed.
(Kukush and Van Huffel [<xref ref-type="bibr" rid="j_vmsta104_ref_010">10</xref>], Theorem 5b).
Let for some r,1≤r<2,supi≥1j=1,…,n+dE|δij|2r<∞,m−1/rλmin(A0⊤A0)→∞asm→∞,λmin2(A0⊤A0)λmax(A0⊤A0)→∞asm→∞.ThenXˆ⟶PX0asm→∞.
Generalizations of Theorems 3.2, 3.3, and 3.4 are obtained in [18]. An essential improvement is achieved. Namely, it is not required that λmin−2(A0⊤A0)λmax(A0⊤A0) converge to 0.
(Shklyar [<xref ref-type="bibr" rid="j_vmsta104_ref_018">18</xref>], Theorem 4.1, generalization of Theorems <xref rid="j_vmsta104_stat_005">3.2</xref> and <xref rid="j_vmsta104_stat_007">3.4</xref>).
Let for some r,1≤r≤2,supi≥1j=1,…,n+dE|δij|2r<∞,m−1/rλmin(A0⊤A0)→∞asm→∞.ThenXˆ⟶PX0asm→∞.
Let for some r (1≤r≤2) andm0≥1,supi≥1j=1,…,n+dE|δij|2r<∞,∑m=m0∞1λminr(A0⊤A0)<∞.ThenXˆ→X0asm→∞, almost surely.
The key point of the proof is the application of our own theorem on perturbation bounds for generalized eigenvectors (Theorems 6.5 and 6.6, see also [18]). The conditions were relaxed by renormalization of the data.
Existence and uniqueness of the estimator
When we speak of sequence {Am,m≥1} of random events parametrized by sample size m, we say that a random event occurs with high probability if the probability of the event tends to 1 as m→∞, and we say that a random event occurs eventually if almost surely there exists m0 such that the random event occurs whenever m>m0{m_{0}}$]]>, that is P(lim infm→∞Am)=1. (In this definition, Am are random events. Elsewhere in this paper, Am are matrices.)
Under the conditions of Theorem3.5, the following three events occur with high probability; under the conditions of Theorem3.6or3.7, the following relations occur eventually.
The constrained minimum in (7) is attained. If Δ satisfies the constraints in (7) (particularly, if matrix Δ is a solution to optimization problem (7)), then the linear equation (8) has a solutionXˆextthat is a full-rank matrix.
The optimization problem (7) has a unique solution Δ.
For any Δ that is a solution to (7), equation (9) (which is a linear equation inXˆ) has a unique solution.
The constrained minimum in (11) is attained. If Δ satisfies the constraints in (11), then the linear equation (8) has a solutionXˆextthat is a full-rank matrix.
Under the conditions of Theorem3.5, the following random event occurs with high probability: for any Δ that is a solution to (11), equation (9) has a solutionXˆ. (Equation (9) might have multiple solutions.) The solution is a consistent estimator ofX0, i.e.,Xˆ→X0in probability.
Under the conditions of Theorem3.6or3.7, the following random event occurs eventually: for any Δ that is a solution to (11), equation (9) has a solutionXˆ. The solution is a strongly consistent estimator ofX0, i.e.,Xˆ→X0almost surely.
Theorem 4.2 can be generalized in the following way: all references to (11) can be changed into references to (12). Thus, if Frobenius norm in the definition of the estimator is changed to any unitarily invariant norm, the consistency results are still valid.
Sketch of the proof of Theorems <xref rid="j_vmsta104_stat_008">3.5</xref>–<xref rid="j_vmsta104_stat_010">3.7</xref>
Denote
N=C0⊤C0+λmin(A0⊤A0)I.
Under the conditions of any of the consistency theorems in Section 3 there is a convergence λmin(A0⊤A0)→∞. Hence the matrix N is nonsingular for m large enough. The matrix N is used as the denominator in the law of large numbers. Also, it is used for rescaling the problem: the condition number of N−1/2C0⊤C0N−1/2 equals 2 at most.
The proofs of consistency theorems differ one from another, but they have the same structure and common parts. First, the law of large numbers
N−1/2(C⊤C−C0⊤C0−mΣ)N−1/2=N−1/2∑i=1m(ci⊤ci−(ci0)⊤ci0−Σ)N−1/2→0
holds either in probability or almost surely, which depends on the theorem being proved. The proof varies for different theorems.
The inequalities (54) and (57) imply that whenever convergence (13) occurs, the sine between vectors Xˆext and Xext0 (in the univariate regression) or the largest of sines of canonical values between column spans of matrices Xˆext and Xext0 tends to 0 as the sample size m increases:
‖sin∠(Xˆext,Xext0)‖≤‖sin∠(N1/2Xˆext,N1/2Xext0)‖→0.
To prove (14), we use some algebra, the fact that Xext0 (in the univariate model) or the columns of Xext0 (in the multivariate model) are the minimum-eigenvalue eigenvectors of matrix N (see ineq. (52)), and eigenvector perturbation theorems – Lemma 6.5 or Lemma 6.6.
Then, by Theorem 8.3 we conclude that
‖Xˆ−X0‖→0.
Relevant classical results
We use some classical results. However, we state them in a form convenient for our study and provide the proof for some of them.
Generalized eigenvectors and eigenvalues
In this paper we deal with real matrices. Most theorems in this section can be generalized for matrices with complex entries by requiring that matrices be Hermitian rather than symmetric, and by complex conjugating where it is necessary.
(Simultaneous diagonalization of a definite matrix pair).
Let A and B ben×nsymmetric matrices such that for some α and β the matrixαA+βBis positive definite. Then there exist a nonsingular matrix T and diagonal matrices Λ and M such thatA=(T−1)⊤ΛT−1,B=(T−1)⊤MT−1.
If in the decomposition T=[u1,u2,…,un], Λ=diag(λ1,…,λn), M=diag(μ1,…,μn), then the numbers λi/μi∈R∪{∞} are called generalized eigenvalues, and the columns ui of the matrix T are called the right generalized eigenvectors of the matrix pencil ⟨A,B⟩ because the following relation holds true:
μiAui=λiBui.
Theorem 6.1 is well known; see Theorem IV.3.5 in [19, page 318]. The conditions of Theorem 6.1 can be changed as follows:
Let A and B be symmetric positive semidefinite matrices. Then there exist a nonsingular matrix T and diagonal matrices Λ and M such thatA=(T−1)⊤ΛT−1,B=(T−1)⊤MT−1.
In Theorem 6.1λi and μi cannot be equal to 0 for the same i, while in Theorem 6.2 they can. On the other hand, in Theorem 6.1λi and μi can be any real numbers, while in Theorem 6.2λi≥0 and μi≥0. Theorem 6.2 is proved in [15].
If the matrices A and B are symmetric and positive semidefinite, then
rk⟨A,B⟩=rk(A+B),
where
rk⟨A,B⟩=maxkrk(A+kB)
is the determinantal rank of the matrix pencil ⟨A,B⟩. (For square n×n matrices A and B, the determinantal rank characterizes if the matrix pencil is regular or singular. The matrix pencil ⟨A,B⟩ is regular if rk⟨A,B⟩=n, and singular if rk⟨A,B⟩<n.)
The inequality rk⟨A,B⟩≥rk(A+B) follows from the definition of the determinantal rank. For all k∈R and for all such vectors x that (A+B)x=0 we have x⊤Ax+x⊤Bx=0, and because of positive semidefiniteness of matrices A and B, x⊤Ax≥0 and x⊤Bx≥0. Thus, x⊤Ax=x⊤Bx=0. Again, due to positive semidefiniteness of A and B, Ax=Bx=0 and (A+kB)x=0. Thus, for all k∈R{x:(A+B)x=0}⊂{x:(A+kB)x=0},rk(A+B)≥rk(A+kB),rk⟨A,B⟩=maxkrk(A+kB)≤rk(A+B),
and (17) is proved.
Let A and B be positive semidefinite matrices of the same size such that rk(A+B)=rk(B). The representation (16) might be not unique. But there exists a representation (16) such that
λi=μi=0ifi=1,…,def(B),μi>0ifi=def(B)+1,…,n,T=[T1n×def(B)T2n×rk(B)],T1⊤T2=0.0\hspace{1em}\text{if}\hspace{1em}i=\operatorname{def}(B)+1,\dots ,n,\\{} T& =\big[\hspace{-0.1667em}\underset{n\times \operatorname{def}(B)}{{T_{1}}}\hspace{0.1667em}\hspace{0.1667em}\underset{n\times \operatorname{rk}(B)}{{T_{2}}}\hspace{-0.1667em}\big],\\{} {T_{1}^{\top }}{T_{2}^{}}& =0.\end{aligned}\]]]>
(Here if the matrix B is nonsingular, then T1 is n×0 empty matrix; if B=0, then T2 is n×0 matrix. In these marginal cases, T1⊤T2 is an empty matrix and is considered to be zero matrix.) The desired representation can be obtained from [2] for S=0 (in de Leeuw’s notation). This representation is constructed as follows. Let the columns of matrix T1 make the orthogonal normalized basis of Ker(B)={v:Bv=0}. There exists n×rk(B) matrix F such that B=FF⊤. Let the columns of matrix L be the orthogonal normalized eigenvectors of the matrix F†A(F†)⊤. Then set T2=(F†)⊤L. Note that the notation S, F and L is borrowed from [2], and is used only once. Elsewhere in the paper, the matrix F will have a different meaning.
Let A and B be symmetric positive semidefinite matrices such thatrk(A+B)=rk(B). In the simultaneous diagonalization in Theorem6.2with Remark6.2-2B†=TM†T⊤,M†=diag(0,…,0︸def(B),μdef(B)+1−1,…,μn−1).
Let us verify the Moore–Penrose conditions: (T−1)⊤MT−1TM†T⊤(T−1)⊤MT−1=(T−1)⊤MT−1,TM†T⊤(T−1)⊤MT−1TM†T⊤=TM†T⊤, and the fact that the matrices (T−1)⊤MT−1TM†T⊤ and TM†T⊤×(T−1)⊤MT−1 are symmetric. The equalities (18) and (19) can be verified directly; and the symmetry properties can be reduced to the equality
(T−1)⊤PMT⊤=TPMT−1
with PM=MM†=diag(0,…,0︸def(B),1,…,1︸rk(B)).
Since T1⊤T2=0, T⊤T is a block diagonal matrix. Hence PMT⊤T=T⊤TPM, whence (20) follows. □
Angle between two linear subspaces
Let V1 and V2 be linear subspaces of Rn, with dimV1=k1≤dimV2=k2. Then there exists an orthogonal n×n matrix U such that V1=spanUdiagk2×k1(cosθi,i=1,…,k1)diag(n−k2)×k1(sinθi,i=1,…,min(n−k2,k1)),V2=spanUIk20(n−k2)×k2. Here rectangular diagonal matrices are allowed. If in (21) there are more cosines than sines (i.e., if k2+k1>nn$]]>), then the excessive cosines should be equal to 1, so the columns of the bidiagonal matrix in (21) are unit vectors (which are orthogonal to each other). Here the columns of U are the vectors of some convenient “new” basis in Rn, so U is a transitional matrix from the standard basis to “new” basis; the columns of matrix products in span⟨⋯⟩ in (21) and (22) are the vectors of the bases of subspaces V1 and V2; the bidiagonal matrix in (21) and the diagonal matrix in (22) are the transitional matrices from “new” basis in Rn to the bases in V1 and V2, respectively.
The angles θk are called the canonical angles between V1 and V2. They can be selected so that 0≤θk≤12π (to achieve this, we might have to reverse some vectors of the bases).
Denote PV1 the matrix of the orthogonal projector onto V1. The singular values of the matrix PV1(I−PV2) are equal to sinθk (k=1,…,k1); besides them, there is a singular value 0 of multiplicity n−k1.
Denote the greatest of the sines of the canonical eigenvalues
‖sin∠(V1,V2)‖=maxk=1,…,k1sinθk=‖PV1(I−PV2)‖.
If dimV1=1, V1=span⟨v⟩, then
sin∠(v,V2)=‖(I−PV2)v‖v‖‖=dist(1‖v‖v,V2).
This can be generalized for dimV1≥1:
‖sin∠(V1,V2)‖=maxv∈V1∖{0}‖(I−PV2)v‖v‖‖,
whence
‖sin∠(V1,V2)‖2=maxv∈V1∖{0}v⊤(I−PV2)v‖v‖2,1−‖sin∠(V1,V2)‖2=minv∈V1∖{0}v⊤PV2v‖v‖2.
If dimV1=dimV2, then ‖sin∠(V1,V2)‖=‖PV1−PV2‖, and therefore ‖sin∠(V1,V2)‖=‖sin∠(V2,V1)‖. Otherwise the right-hand side of (23) may change if V1 and V2 are swapped (particularly, if dimV1<dimV2, then ‖PV1(I−PV2)‖ may or may not be equal to 1, but always ‖PV2(I−PV1)‖=1; see the proof of Lemma 8.2 in the appendix).
We will often omit “span” in arguments of sine. Thus, for n-row matrices X1 and X2, ‖sin∠(X1,V2)‖=‖sin∠(span⟨X1⟩,V2)‖ and ‖sin∠(X1,X2)‖=‖sin∠(span⟨X1⟩,span⟨X2⟩)‖.
LetV11,V2andV13be three linear subspaces inRn, withdimV11=d1<dimV2=d2<dimV13=d3andV11⊂V13. Then there exists such a linear subspaceV12⊂RnthatV11⊂V12⊂V13,dimV12=d2, and‖sin∠(V12,V2)‖=1.
Since dimV13+dimV2⊥=d3+n−d2>nn$]]>, there exists a vector v≠0, v∈V13∩V2⊥. Since max(d1,1)≤dimspan⟨V11,v⟩≤d1+1, it holds that
dimspan⟨V11,v⟩≤d2<dimV13.
Therefore, there exists a d2-dimensional subspace V12 such that span⟨V11,v⟩⊂V12⊂V13. Then V11⊂V12⊂V13 and v∈V12∩V2⊥. Hence PV12(I−PV2)v=v, ‖PV12(I−PV2)‖≥1, and due to equation (23), ‖sin∠(V12,V2)‖=1. Thus, the subspace V12 has the desired properties. □
Perturbation of eigenvectors and invariant spaces
Let A, B,A˜be symmetric matrices,λmin(A)=0,λ2(A)>00$]]>andλmin(B)≥0. LetAx0=0andBx0≠0(sox0is an eigenvector of the matrix A that corresponds to the minimum eigenvalue). Let minimum of the functionf(x):=x⊤(A+A˜)xx⊤Bx,x⊤Bx>0,0,\]]]>be attained at the pointx∗. Thensin2∠(x∗,x0)≤‖A˜‖λ2(A)(1+‖x0‖2x0⊤Bx0x⊤Bx‖x‖2).
The function f(x) may or may not attain the minimum. Thus the condition f(x∗)=minx⊤Bx>0f(x)0}}f(x)$]]> sometimes cannot be satisfied. But the theorem is still true if
lim infx→x∗f(x)=infx:x⊤Bx>0f(x)0}{\inf }f(x)\]]]>
and x∗≠0.
Now proclaim the multivariate generalization of Lemma 6.5. We will not generalize Remark 6.5-1. Instead, we will check that the minimum is attained when we use Lemma 6.6 (see Proposition 7.10).
Let A, B,A˜ben×nsymmetric matrices,λi(A)=0for alli=1,…,d,λd+1(A)>00$]]>,λmin(B)≥0. LetX0ben×dmatrix such thatAX0=0and the matrixX0⊤BX0is nonsingular. Let the functionalf(X)=λmax((X⊤BX)−1X⊤(A+A˜)X)ifX∈Rn×dandX⊤BX>0,f(X)is not defined otherwise,0\textit{,}\\{} f(X)& \hspace{0.2778em}\textit{is not defined otherwise,}\end{aligned}\]]]>attain its minimum. Then for any point X where the minimum is attained,‖sin∠(X,X0)‖2≤‖A˜‖λd+1(A)(1+‖B‖λmax((X0⊤BX0)−1X0⊤X0)).
Rosenthal inequality
In the following theorems, a random variable ξ is called centered if Eξ=0.
Letν≥2be a nonrandom real number. Then there existα≥0andβ≥0such that for any set of centered mutually independent random variables{ξi,i=1,…,m},m≥1, the following inequality holds true:E[|∑i=1mξi|ν]≤α∑i=1mE[|ξi|ν]+β(∑i=1mEξi2)ν/2.
Theorem 6.7 is well known; see [16, Theorem 2.9, page 59].
Let ν be a nonrandom real number,1≤ν≤2. Then there existsα≥0such that for any set of centered mutually independent random variables{ξi,i=1,…,m},m≥1, the inequality holds true:E[|∑i=1mξi|ν]≤α∑i=1mE[|ξi|ν].
The desired inequality is trivial for ν=1. For all 1<ν≤2 it is a consequence of the Marcinkiewicz–Zygmund inequality
E[|∑i=1mξi|ν]≤αE[(∑i=1mξi2)ν/2]≤αE∑i=1m|ξi|ν=α∑i=1mE|ξi|ν.
Here the first inequality is due to Marcinkiewicz and Zygmund [11, Theorem 13]. The second inequality follows from the fact that for ν≤2,
(∑i=1mξi2)ν/2≤∑i=1m|ξi|ν.
□
Generalized eigenvalue problem for positive semidefinite matrices
In this section we explain the relationship between the TLS estimator and the generalized eigenvalue problem. The results of this section are important for constructing the TLS estimator. Proposition 7.9 is used to state the uniqueness of the TLS estimator.
Let A and B ben×nsymmetric positive semidefinite matrices, with simultaneous diagonalizationA=(T−1)⊤ΛT−1,B=(T−1)⊤MT−1,withΛ=diag(λ1,…,λn),M=diag(μ1,…,μn)(see Theorem6.2for its existence). Fori=1,…,ndenoteνi=λi/μiifμi>0,0ifλi=0,+∞ifλi>0,μi=0.0\textit{,}\\{} 0\hspace{1em}& \textit{if}\hspace{2.5pt}{\lambda _{i}}=0\textit{,}\\{} +\infty \hspace{1em}& \textit{if}\hspace{2.5pt}{\lambda _{i}}>0\textit{,}\hspace{2.5pt}{\mu _{i}}=0\textit{.}\end{array}\right.\]]]>Assume thatν1≤ν2≤⋯≤νn. Thenνi=min{λ≥0|“∃V,dimV=i:(A−λB)|V≤0”},i.e.,νiis the smallest numberλ≥0, such that there exists an i-dimensional subspaceV⊂Rn, such that the quadratic formA−λBis negative semidefinite on V.
νi<∞ if and only if
∃λ∃V,dimV=i:(A−λB)|V≤0.
Let νi<∞. The minimum in (27) is attained for V being the linear span of first i columns of the matrix T (i.e., the linear span of the eigenvectors of the matrix pencil ⟨A,B⟩ that correspond to the i smallest generalized eigenvalues). That is
(A−νiB)|V≤0forV=span⟨T(Ik0(n−k)×k)⟩.
In Propositions 7.2–7.5 the following optimization problem is considered. For a fixed (n+d)×d matrix X find an m×(n+d) matrix Δ where the constrained minimum is attained:
ΔΣ†Δ⊤→min;Δ(I−PΣ)=0;(C−Δ)X=0.
Here the matrix X is assumed to be of full rank:
rkX=d.
1. The constraints in (28) are compatible if and only ifspan⟨X⊤C⊤⟩⊂span⟨X⊤Σ⟩.Herespan⟨M⟩is a column space of the matrix M.
2. Let the constraints in (28) be compatible. Then the least element of the partially ordered set (in the Loewner order){ΔΣ†Δ⊤:Δ(I−PΣ)=0and(C−Δ)X=0}is attained forΔ=CX(X⊤ΣX)†X⊤Σand is equal toCX(X⊤ΣX)†X⊤C⊤. This means the following:
2a. ForΔ=CX(X⊤ΣX)†X⊤Σ, it holds thatΔ(I−PΣ)=0,(C−Δ)X=0,ΔΣ†Δ⊤=CX(X⊤ΣX)†X⊤C⊤;
2b. For any Δ which satisfies the constraintsΔ(I−PΣ)=0and(C−Δ)X=0,ΔΣ†Δ⊤≥CX(X⊤ΣX)†X⊤C⊤.
If the constraints are compatible, the least element (and the unique minimum) is attained at a single point. Namely, the equalities
Δ(I−PΣ)=0,(C−Δ)X=0,ΔΣ†Δ⊤=CX(X⊤ΣX)†X⊤C⊤
imply Δ=CX(X⊤ΣX)†X⊤Σ.
Let the matrix pencil⟨C⊤C,Σ⟩be definite and (29) hold. The constraints in (28) are compatible if and only if the matrixX⊤ΣXis nonsingular. Then Proposition7.2still holds true if(X⊤ΣX)−1is substituted for(X⊤ΣX)†.
Let X be an(n+d)×dmatrix which satisfies (29) and makes the constraints in (28) compatible. Then fork=1,2,…,d,minΔ(I−PΣ)=0(C−Δ)X=0λk+m−d(ΔΣ†Δ⊤)=min{λ≥0:“∃V⊂span⟨X⟩,dimV=k:(C⊤C−λΣ)|V≤0”}.
In the left-hand side of (34) the minima are attained for the same Δ=CX(X⊤ΣX)†X⊤Σ for all k (the k sets where the minima are attained have non-empty intersection; we will show that the intersection comprises of a single element).
One can choose a stack of subspaces
V1⊂V2⊂⋯⊂Vd=span⟨X⟩
such that Vk is the element where the minimum in the right-hand side of (34) is attained, i.e., for all k=1,…,d,
dimVk=k,Vk⊂span⟨X⟩,(C⊤C−νkΣ)|Vk≤0,
with νk=minΔ(I−PΣ)=0(C−Δ)X=0λk+m−d(ΔΣ†Δ⊤).
In Propositions 7.5 to 7.9, we will use notation from simultaneous diagonalization of matrices C⊤C and Σ:
C⊤C=(T−1)⊤ΛT−1,Σ=(T−1)⊤MT−1,
where
Λ=diag(λ1,…,λn+d),M=diag(μ1,…,μn+d),T=[u1,u2,…,ud,…,un+d].
If Remark 6.2-2 is applicable, let the simultaneous diagonalization be constructed accordingly. For k=1,…,n+d denote
νi=λk/μkifμk>0,0ifλk=0,+∞ifλk>0,μk=0.0\text{,}\\{} 0\hspace{1em}& \text{if}\hspace{2.5pt}{\lambda _{k}}=0\text{,}\\{} +\infty \hspace{1em}& \text{if}\hspace{2.5pt}{\lambda _{k}}>0\text{,}\hspace{2.5pt}{\mu _{k}}=0\text{.}\end{array}\right.\]]]>
Let νk be arranged in ascending order.
Let X be an(n+d)×dmatrix which satisfies (29) and makes constraints in (28) compatible. ThenminΔ(I−PΣ)=0(C−Δ)X=0λk+m−d(ΔΣ†Δ⊤)≥νk.
Ifνd<∞, then forX=[u1,u2,…,ud]the inequality in (36) becomes an equality.
In the minimization problem (11), the constrained minimum is equal tominΔ(I−PΣ)=0rk(C−Δ)≤nλmax(ΔΣ†Δ⊤)=νd.
In the minimization problem (7) the constrained minimum is equal tominΔ(I−PΣ)=0rk(C−Δ)≤n‖(ΔΣ1/2)†‖F=∑k=1dνk.
Whenever the minimum in (7) is attained for some matrix Δ, the minimum in (11) is attained for the same Δ.
Let‖M‖Ube an arbitrary unitarily invariant norm onm×nmatrices. Singular values of the matrix M are arranged in descending order and denotedσi(M):σ1(M)≥σ2(M)≥⋯≥σmin(m,n)(M)≥0.LetM1andM2bem×nmatrices. Then
Consider the optimization problem (12) with arbitrary unitarily invariant norm‖M‖U. Then
Any minimizer Δ to the optimization problem (7) also minimizes (12).
Any minimizer Δ to the optimization problem (12) also minimizes (11).
For any Δ where the minimum in (7) is attained and the corresponding solutionXˆextof the linear equations (8) (Xˆextis an(n+d)×dmatrix of rank d), it holds thatspan⟨ui:νi<νd⟩⊂span⟨Xˆext⟩⊂span⟨ui:νi≤νd⟩.
Conversely, ifνd<+∞and the matrixXˆextsatisfies conditions (37), then there exists a common solution Δ to the minimization problem (7) and the linear equations (8).
As a consequence, if νd<νd+1, then (7) and (8) unambiguously determine span⟨Xˆext⟩ of rank d.
Let⟨C⊤C,Σ⟩be a definite matrix pencil. Then for any Δ where the minimum in (11) is attained, the corresponding solutionXˆextof the linear equations (8) (such thatrkXˆext=d) is a point where the minimum of the functionalX↦λmax((X⊤ΣX)−1X⊤C⊤CX),X∈R(n+d)×d,X⊤ΣX>0,0,\]]]>is attained. It is also a point where the minimum ofX↦λmax((X⊤ΣX)−1X⊤(C⊤C−mΣ)X),is attained.
The functional (39) equals the functional (38) minus m.
Appendix: ProofsDetailed proofs of Theorems <xref rid="j_vmsta104_stat_008">3.5</xref>–<xref rid="j_vmsta104_stat_010">3.7</xref>Bounds for eigenvalues of some matrices used in the proofEigenvalues of the matrix <inline-formula id="j_vmsta104_ineq_421"><alternatives>
<mml:math><mml:msubsup><mml:mrow><mml:mi mathvariant="italic">C</mml:mi></mml:mrow><mml:mrow><mml:mn>0</mml:mn></mml:mrow><mml:mrow><mml:mo>⊤</mml:mo></mml:mrow></mml:msubsup><mml:msubsup><mml:mrow><mml:mi mathvariant="italic">C</mml:mi></mml:mrow><mml:mrow><mml:mn>0</mml:mn></mml:mrow><mml:mrow/></mml:msubsup></mml:math>
<tex-math><![CDATA[${C_{0}^{\top }}{C_{0}^{}}$]]></tex-math></alternatives></inline-formula>
The (n+d)×(n+d) matrix C0⊤C0 is symmetric and positive semidefinite. Since C0Xext0=A0X0−B0=0, the matrix C0⊤C0 is rank deficient with eigenvalue 0 of multiplicity at least d. As A0⊤A0 is a n×n principal submatrix of C0⊤C0,
λd+1(C0⊤C0)≥λmin(A0⊤A0)
by the Cauchy interlacing theorem (Theorem IV.4.2 from [19] used d times).
Due to inequality (40), if the matrix A0⊤A0 is nonsingular, then λn+1(C0⊤C0)>00$]]>, whence rk(C0⊤C0)=d. If the conditions of Theorem 3.5, 3.6 or 3.7 hold true, then λmin(A0⊤A0)→∞, and thus
λd+1(C0⊤C0)≥λmin(A0⊤A0)>00\]]]>
for m large enough.
If conditions (4)–(6) hold true, and conditions of either of Theorems3.5,3.6, or3.7hold true, then for m large enough⟨C⊤C,Σ⟩is a definite matrix pencil almost surely. More specifically,∃m0∀m>m0:P(C⊤C+Σ>0)=1.{m_{0}}:\hspace{0.2778em}\mathbb{P}\big({C}^{\top }C+\varSigma >0\big)=1.\]]]>
1. If the matrix Σ is nonsingular, then Proposition 8.1 is obvious. Due to condition (6), rkΣ≥d (see Remark 2.1), whence Σ≠0. In what follows, assume that Σ is a singular but non-zero matrix. Let F=(F1F2) be a (n+d)×(n+d−rk(Σ)) matrix whose columns make the basis of the null-space Ker(Σ)={x:Σx=0} of the matrix Σ.
2. Now prove that columns of the matrix [InX0]F are linearly independent. Assume the contrary. Then for some v∈Rn+d−rk(Σ)∖{0}, [InX0]Fv=0,F1v=−X0F2v,Fv=(X0−Id)F2v=Xext0F2v,0=ΣFv=ΣXext0·F2v.
Furthermore, Fv≠0 because v≠0 and the columns of F are linearly independent. Hence, by (41), F2v≠0.
Equality (42) implies that the columns of the matrix ΣXext0 are linearly dependent, and this contradicts condition (6). The contradiction means that columns of the matrix [IXext0]F are linearly independent.
3. If the conditions of either Theorem 3.5, 3.6, or 3.7 hold true, then the matrix A0⊤A0 is positive definite for m large enough.
4. Under conditions (4) and (5), C˜F=0 almost surely. Indeed, Ec˜i=0 and var[c˜iF]=F⊤ΣF=0, i=1,2,…,m.
5. It remains to prove the implication:
ifA0⊤A0>0andC˜F=0,thenC⊤C+Σ>0.0\hspace{1em}\text{and}\hspace{1em}\tilde{C}F=0,\hspace{1em}\text{then}\hspace{1em}{C}^{\top }C+\varSigma >0.\]]]>
The matrices C⊤C and Σ are positive semidefinite. Suppose that x⊤(C⊤C+Σ)x=0 and prove that x=0. Since x⊤(C⊤C+Σ)x=0, Cx=0 and Σx=0. The vector x belongs to the null-space of the matrix Σ. Therefore, x=Fv for some vector v∈Rn+d−rkΣ. Then
0=A0⊤Cx=A0(C0+C˜)x=A0C0Fv+A0C˜Fv=A0⊤A0[InX0]Fv+0.
As the matrix A0⊤A0 is nonsingular and columns of the matrix [InX0]F are linearly independent, the columns of the matrix A0⊤A0[InX0]F are linearly independent as well. Hence, (43) implies v=0, and so x=Fv=0.
We have proved that the equality x⊤(C⊤C+Σ)x=0 implies x=0. Thus, the positive semidefinite matrix C⊤C+Σ is nonsingular, and so positive definite. □
Eigenvalues and common eigenvectors of <italic>N</italic> and <inline-formula id="j_vmsta104_ineq_467"><alternatives>
<mml:math><mml:msup><mml:mrow><mml:mi mathvariant="italic">N</mml:mi></mml:mrow><mml:mrow><mml:mo>−</mml:mo><mml:mstyle displaystyle="false"><mml:mfrac><mml:mrow><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac></mml:mstyle></mml:mrow></mml:msup><mml:msubsup><mml:mrow><mml:mi mathvariant="italic">C</mml:mi></mml:mrow><mml:mrow><mml:mn>0</mml:mn></mml:mrow><mml:mrow><mml:mo>⊤</mml:mo></mml:mrow></mml:msubsup><mml:msubsup><mml:mrow><mml:mi mathvariant="italic">C</mml:mi></mml:mrow><mml:mrow><mml:mn>0</mml:mn></mml:mrow><mml:mrow/></mml:msubsup><mml:msup><mml:mrow><mml:mi mathvariant="italic">N</mml:mi></mml:mrow><mml:mrow><mml:mo>−</mml:mo><mml:mstyle displaystyle="false"><mml:mfrac><mml:mrow><mml:mn>1</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac></mml:mstyle></mml:mrow></mml:msup></mml:math>
<tex-math><![CDATA[${N}^{-\frac{1}{2}}{C_{0}^{\top }}{C_{0}^{}}{N}^{-\frac{1}{2}}$]]></tex-math></alternatives></inline-formula>
The rank-deficient positive semidefinite symmetric matrix C0⊤C0 can be factorized as:
C0⊤C0=Udiag(λmin(C0⊤C0),λ2(C0⊤C0),…,λn+d(C0⊤C0))U⊤=Udiag(λj(C0⊤C0);j=1,…,n+d)U⊤,
with an orthogonal matrix U and
λmin(C0⊤C0)=λ2(C0⊤C0)=⋯=λd(C0⊤C0)=0.
Then the eigendecomposition of the matrix N=C0⊤C0+λmin(A0⊤A0)I is
N=Udiag(λj(C0⊤C0)+λmin(A0⊤A0);j=1,…,n+d)U⊤.
Notice that
λmin(N)=⋯=λd(N)=λmin(A0⊤A0).
The matrix N is nonsingular as soon as A0⊤A0 is nonsingular. Hence, under the conditions of Theorem 3.5, 3.6, or 3.7, the matrix N is nonsingular for m large enough.
Since C0Xext0=0, it holds that
NXext0=λmin(A0⊤A0)Xext0.
As soon as N is nonsingular, the matrices N−1/2 and N−1/2C0⊤C0N−1/2 have the eigendecomposition
N−1/2=Udiag(1λj(C0⊤C0)+λmin(A0⊤A0);j=1,…,n+d)U⊤,N−1/2C0⊤C0N−1/2=Udiag(λj(C0⊤C0)λj(C0⊤C0)+λmin(A0⊤A0);j=1,…,n+d)U⊤.
Thus, the eigenvalues of N−1/2 and N−1/2C0⊤C0N−1/2 satisfy the following: ‖N−1/2‖=λmax(N−1/2)=1λmin(A0⊤A0);λj(N−1/2C0⊤C0N−1/2)=0,j=1,…,d;12≤λj(N−1/2C0⊤C0N−1/2)≤1,j=d+1,…,n+d. As a result,
12n≤tr(N−1/2C0⊤C0N−1/2)≤n.
Because tr(C0N−1C0⊤)=tr(C0N−1/2N−1/2C0⊤)=tr(N−1/2C0⊤C0N−1/2),
12n≤tr(C0N−1C0⊤)≤n.
These properties will be used in Sections 8.2 and 8.3.
Use of eigenvector perturbation theoremsUnivariate regression (<inline-formula id="j_vmsta104_ineq_477"><alternatives>
<mml:math><mml:mi mathvariant="italic">d</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:math>
<tex-math><![CDATA[$d=1$]]></tex-math></alternatives></inline-formula>)
Remember inequalities (44) (whence (51) follows) and (45):
Xˆext⊤NXˆext≥λmin(A0⊤A0)Xˆext⊤Xˆext;NXext0=λmin(A0⊤A0)Xext0.
Then
(Xˆext⊤Xext0)2Xˆext⊤Xˆext·Xext0⊤Xext0≥(Xˆext⊤NXext0)2Xˆext⊤NXˆext·Xext0⊤NXext0,cos2∠(Xˆext,Xext0)≥cos2∠(N1/2Xˆext,N1/2Xext0),sin2∠(Xˆext,Xext0)≤sin2∠(N1/2Xˆext,N1/2Xext0).
Now, apply Lemma 6.5 on the perturbation bound for the minimum-eigenvalue eigenvector. The unperturbed symmetric matrix is N−1/2C0⊤C0N−1/2, satisfying
λmin(N−1/2C0⊤C0N−1/2)=0,N−1/2C0⊤C0N−1/2N1/2Xext0=0,λ2(N−1/2C0⊤C0N−1/2)≥12.
The null-vector of the unperturbed matrix is N−1/2Xext0.
The column vector Xˆext is a generalized eigenvector of the matrix pencil ⟨C⊤C,Σ⟩. Denote the corresponding eigenvalue by λmin. Thus,
C⊤CXˆext=λmin·ΣXˆext.
The perturbed matrix is N−1/2(C⊤C−mΣ)N−1/2; the minimum eigenvalue of the matrix pencil ⟨N−1/2(C⊤C−mΣ)N−1/2,N−1/2ΣN−1/2⟩ is equal to λmin−m, and the eigenvector is N1/2Xˆext:
N−1/2(C⊤C−mΣ)N−1/2N1/2Xˆext=(λmin−m)N−1/2ΣN−1/2N1/2Xˆext.
We have to verify that N−1/2ΣN−1/2N1/2Xext0≠0; this follows from condition (6). Obviously, the matrix N−1/2ΣN−1/2 is positive semidefinite:
N−1/2ΣN−1/2≥0.
Denote
ϵ=‖N−1/2(C⊤C−mΣ)N−1/2−N−1/2C0⊤C0N−1/2‖.
By Lemma 6.5sin2∠(N1/2Xˆext,N1/2Xext0)≤ϵ0.5(1+Xext0⊤NXext0Xext0⊤ΣXext0·Xˆext⊤ΣXˆextXˆext⊤NXˆext).
Use (45) and (51) again, and also use (52):
sin2∠(Xˆext,Xext0)≤sin2∠(N1/2Xˆext,N1/2Xext0)≤2ϵ(1+Xext0⊤Xext0Xext0⊤ΣXext0·Xˆext⊤ΣXˆextXˆext⊤Xˆext)≤2ϵ(1+Xext0⊤Xext0·‖Σ‖Xext0⊤ΣXext0).
What follows is valid for both univariate (d=1) and multivariate (d>11$]]>) regression.
Due to (44), N≥λmin(A0⊤A0)I in the Loewner order; thus inequality (51) holds in the Loewner order. Hence
∀v∈Rd∖{0}:v⊤Xˆext⊤Xext0(Xext0⊤Xext0)−1Xext0⊤Xˆextvv⊤Xˆext⊤Xˆextv≥λmin(A0⊤A0)v⊤Xˆext⊤Xext0(Xext0⊤Xext0)−1Xext0⊤Xˆextvv⊤Xˆext⊤NXˆextv.
With inequality (45), we get
v⊤Xˆext⊤Xext0(Xext0⊤Xext0)−1Xext0⊤Xˆextvv⊤Xˆext⊤Xˆextv≥v⊤NXˆext⊤Xext0(Xext0⊤NXext0)−1Xext0⊤NXˆextvv⊤Xˆext⊤NXˆextv.
Using equation (24) to determine the sine and noticing that
PXext0=Xext0(Xext0⊤Xext0)−1Xext0⊤,PN1/2Xext0=N1/2Xext0(Xext0⊤NXext0)−1Xext0⊤N1/2,
we get
1−‖sin∠(Xˆext,Xext0)‖2≥1−‖sin∠(N1/2Xˆext,N1/2Xext0)‖2,‖sin∠(Xˆext,Xext0)‖≤‖sin∠(N1/2Xˆext,N1/2Xext0)‖.
The TLS estimator Xˆext is defined as a solution to the linear equations (8) for Δ that brings the minimum to (7). By Proposition 7.6, the same Δ brings the minimum to (11). By Proposition 7.10, the functions (38) and (39) attain their minima at the point Xˆext. Therefore, the minimum of the function
M↦λmax((M⊤N−1/2ΣN−1/2M)−1M⊤N−1/2(C⊤C−mΣ)N−1/2M)
is attained for M=N1/2Xˆext.
Now, apply Lemma 6.6 on perturbation bounds for a generalized invariant subspace. The unperturbed matrix (denoted A in Lemma 6.6) is N−1/2C0⊤C0N−1/2; its nullspace is the column space of the matrix N1/2Xext0 (which is denoted X0 in Lemma 6.6). The perturbed matrix (A+A˜ in Lemma 6.6) is N−1/2(C⊤C−mΣ)N−1/2. The matrix B in Lemma 6.6 equals N−1/2ΣN−1/2. The norm of the perturbation is denoted ϵ (it is ‖A˜‖ in Lemma 6.6). The (n+d)×d matrix which brings the minimum to (56) is N1/2Xˆext. The other conditions of Lemma 6.6 are (47), (48), and (53). We have
‖sin∠(N1/2Xˆext,N1/2Xext0)‖2≤ϵ0.5(1+‖N−1/2ΣN−1/2‖λmax((Xext0⊤ΣXext0)−1Xext0⊤NXext0)).
Again, with (55), (45) and (46), we have
‖sin∠(Xˆext,Xext0)‖2≤‖sin∠(N1/2Xˆext,N1/2Xext0)‖2≤2ϵ(1+‖Σ‖λmin(A0⊤A0)λmax(λmin(A0⊤A0)(Xext0⊤ΣXext0)−1Xext0⊤Xext0))=2ϵ(1+‖Σ‖λmax((Xext0⊤ΣXext0)−1Xext0⊤Xext0)).
Proof of the convergence <inline-formula id="j_vmsta104_ineq_505"><alternatives>
<mml:math><mml:mi mathvariant="italic">ϵ</mml:mi><mml:mo stretchy="false">→</mml:mo><mml:mn>0</mml:mn></mml:math>
<tex-math><![CDATA[$\epsilon \to 0$]]></tex-math></alternatives></inline-formula>
In this section, we prove the convergences
M1=N−1/2C0⊤C˜N−1/2→0,M2=N−1/2(C˜⊤C˜−mΣ)N−1/2→0
in probability for Theorem 3.5, and almost surely for Theorems 3.6 and 3.7. As ϵ=‖M1+M1⊤+M2‖, the convergences M1→0 and M2→0 imply ϵ→0.
It holds that
‖M1‖F2=‖N−1/2C0⊤C˜N−1/2‖F2=tr(N−1/2C0⊤C˜N−1C0C˜⊤N−1/2)=tr(C0N−1C0⊤C˜N−1C˜⊤)=∑i=1m∑j=1mci0N−1(cj0)⊤c˜jN−1c˜i⊤.
The right-hand side can be simplified since Ec˜jN−1c˜i⊤=0 for i≠j and Ec˜iN−1c˜i⊤=tr(ΣN−1):
E‖M1‖F2=∑i=1mc0iN−1c0i⊤tr(ΣN−1)=tr(C0N−1C0⊤)tr(ΣN−1).
The first multiplier in the right-hand side is bounded due to (50) as tr(C0N−1C0⊤)≤n, for m large enough. Now, construct an upper bound for the second multiplier:
tr(ΣN−1)=‖N−1/2Σ1/2‖F2≤‖N−1/2‖2‖Σ1/2‖F2=λmax(N−1)trΣ=trΣλmin(N)=trΣλmin(A0⊤A0).
Finally,
E‖M1‖F2≤ntrΣλmin(A0⊤A0).
The conditions of Theorem 3.5 imply that λmax(A0⊤A0)→∞; therefore, M1⟶P0 as m→∞.
Now, we prove that M2⟶P0 as m→∞. We have
M2=N−1/2(C˜⊤C˜−mΣ)N−1/2,‖M2‖≤‖N−1/2‖‖C˜⊤C˜−mΣ‖‖N−1/2‖=‖∑i=1m(c˜i⊤c˜i−Σ)‖λmin(A0⊤A0).
Now apply the Rosenthal inequality (case 1≤ν≤2; Theorem 6.8) to construct a bound for E‖M2‖r:
E‖M2‖r≤const∑i=1mE‖c˜i⊤c˜i−Σ‖rλminr(A0⊤A0).
By the conditions of Theorem 3.5, the sequence {E‖c˜i⊤c˜i−Σ‖r,i=1,2,…} is bounded. Hence
E‖M2‖r≤O(m)λminr(A0⊤A0)asm→∞,E‖M2‖r→0andM2⟶P0asm→∞.
□
M1=∑i=1mN−1/2c0i⊤c˜iN−1/2.
By the Rosenthal inequality (case ν≥2; Theorem 6.7)
E‖M1‖2r≤const∑i=1mE‖N−1/2c0i⊤c˜iN−1/2‖2r++const(∑i=1mE‖N−1/2c0i⊤c˜iN−1/2‖2)r.
Construct an upper bound for the first summand:
∑i=1mE‖N−1/2c0i⊤c˜iN−1/2‖2r≤∑i=1m‖N−1/2c0i⊤‖2rmaxi=1,…,mE‖c˜i‖2r‖N−1/2‖2r,∑i=1m‖N−1/2c0i⊤‖2r≤(∑i=1m‖N−1/2c0i⊤‖2)r=(∑i=1mc0iN−1c0i⊤)r=(tr(C0N−1C0⊤))r≤nr
by inequality (50). By the conditions of Theorem 3.6, the sequence {maxi=1,…,mE‖c˜i‖2r,m=1,2,…} is bounded. Remember that ‖N−1/2‖=λmin−1/2(A0⊤A0). Thus,
∑i=1mE‖N−1/2c0i⊤c˜iN−1/2‖2r=O(1)λminr(A0⊤A0)asm→∞.
The asymptotic relation
∑i=1mE‖N−1/2c0i⊤c˜iN−1/2‖2=O(1)λmin(A0⊤A0)
can be proved similarly; in order to prove it, we use boundedness of the sequence {maxi=1,…,mE‖c˜i‖2,m=1,2,…}. Finally,
E‖M1‖2r=O(1)λminr(A0⊤A0)asm→∞.
The conditions of Theorem 3.6 imply that ∑m=m0∞E‖M1‖2r<∞, whence M1→0 as m→∞, almost surely.
Now, prove that M2→0 almost surely. In order to construct a bound for E‖M2‖r, use the Rosenthal inequality (case ν≥2; Theorem 6.7) as well as (58):
E‖M2‖r≤E‖∑i=1m(ci⊤c˜i−Σ)‖rλminr(A0⊤A0)≤const∑i=1mE‖c˜i⊤c˜i−Σ‖rλminr(A0⊤A0)+const(∑i=1mE‖c˜i⊤c˜i−Σ‖2)r/2λminr(A0⊤A0).
Under the conditions of Theorem 3.6, the sequences {E‖c˜i⊤c˜i−Σ‖r,i=1,2,…} and {E‖c˜i⊤c˜i−Σ‖2,i=1,2,…} are bounded. Thus,
E‖M2‖r=O(mr/2)λminr(A0⊤A0)asm→∞;∑m=m0∞E‖M2‖r<∞,
whence M2→0 as m→∞, almost surely. □
The proof of the asymptotic relation
E‖M1‖2r=O(1)λminr(A0⊤A0)asm→∞
from Theorem 3.6 is still valid. The almost sure convergence M1→0 as m→∞ is proved in the same way as in Theorem 3.6.
Now, show that M2→0 as m→∞, almost surely. Under the condition of Theorem 3.7,
E‖c˜m⊤c˜m−Σ‖r=O(1),∑m=m0∞E‖c˜m⊤c˜m−Σ‖rλminr(A0⊤A0)<∞,
and Ec˜i⊤c˜i−Σ=0. The sequence of nonnegative numbers {λmin(A0⊤A0),m=1,2,…} never decreases and tends to +∞. Then, by the Law of large numbers in [16, Theorem 6.6, page 209]
1λmin(A0⊤A0)∑i=1m(c˜i⊤c˜i−Σ)→0asm→∞,a.s.,
whence, with (58),
‖M2‖≤‖∑i=1m(c˜i⊤c˜i−Σ)‖λmin(A0⊤A0)→0asm→∞, a.s.;M2→0asm→∞,a.s.
□
Proof of the uniqueness theorems
The random events 1, 2 and 3 are defined in the statement of this theorem on page . The random event 1 always occurs. This was proved in Section 2.2 where the estimator Xˆext is defined. In order to prove the rest, we first construct the random event (59), which occurs either with high probability or eventually. Then we prove that, whenever (59) occurs, there is the existence and “more than uniqueness” in the random event 3, and then prove that the random event 2 occurs.
Now, we construct a modified version Xˆextmod of the estimator Xˆext in the following way. If there exist such solutions (Δ,Xˆext) to (7) & (8) that ‖sin∠(Xˆext,Xext0)‖≥(1+‖X0‖2)−1/2, let Xˆextmod come from one of such solutions. Otherwise, if for every solution (Δ,Xˆext) to (7) & (8) ‖sin∠(Xˆext,Xext0)‖<(1+‖X0‖2)−1/2, let Xˆextmod come from one of these solutions. In any case, let us construct Xˆextmod in such a way that it is a random matrix. It is possible; that follows from [17].
Thus we construct a matrix Xˆextmod such that:
Xˆextmod is a (d+n)×n random matrix;
for some Δ∈Rm×(d+n), (Δ,Xˆextmod) is a solution to (7) & (8);
if ‖sin∠(Xˆextmod,Xext0)‖<(1+‖X0‖2)−1/2, then ‖sin∠(Xˆext,Xext0)‖<(1+‖X0‖2)−1/2 for any solution (Δ,Xˆext) to (7) & (8).
From the proof of Theorem 3.5 it follows that ‖sin∠(Xˆextmod,Xext0)‖→0 in probability as m→∞. From the proof of Theorem 3.6 or 3.7 it follows that ‖sin∠(Xˆextmod,Xext0)‖→0 almost surely. Then
‖sin∠(Xˆextmod,Xext0)‖<11+‖X0‖2
either with high probability or almost surely.
Whenever the random event (59) occurs, for any solution Δ to (7) and the corresponding full-rank solution Xˆext to (8) (which always exists) it holds that ‖sin∠(Xˆext,Xext0)‖<(1+‖X0‖2)−1/2, whence, due to Theorem 8.3, the bottom d×d block of the matrix Xˆext is nonsingular. Right-multiplying Xˆext by a nonsingular matrix, we can transform it into a form (Xˆ−I). The constructed matrix Xˆ is a solution to equation (9) for given Δ. Thus, we have just proved that if the random event (59) occurs, then for any Δ which is a solution to (7), equation (9) has a solution.
Now, prove the uniqueness of Xˆ. Let (Δ1,Xˆ1) and (Δ2,Xˆ2) be two solutions to (7) & (9). Show that Xˆ1=Xˆ2. (If we can for Δ1=Δ2, then the random event 3 occurs.) Denote Xˆ1ext=(Xˆ1−I) and Xˆ2ext=(Xˆ2−I). By Proposition 7.9, span⟨Xˆ1ext⟩⊂span⟨uk,νk≤d⟩ and span⟨Xˆ2ext⟩⊂span⟨uk,νk≤d⟩, where νk and uk are generalized eigenvalues (arranged in ascending order) and respective eigenvectors of the matrix pencil ⟨X⊤X,Σ⟩.
Assume by contradiction that Xˆ1≠Xˆ2. Then rk[Xˆ1ext,Xˆ2ext]≥d+1, where [Xˆ1ext,Xˆ2ext] is an (n+d)×2d matrix constructed of Xˆ1ext and Xˆ2ext. Then
d∗=rk⟨uk,νk≤d⟩≥rkXˆ1ext,Xˆ2ext≥d+1
(which means νd=νd+1). Then d∗−1<d<d∗, where d∗−1=dimspan⟨uk,νk<d⟩, d=dimspan⟨Xext0⟩ and d∗=dimspan⟨uk,νk≤d⟩ (notation d∗ and d∗ comes from the proof of Proposition 7.9). By Lemma 6.4, there exists a d-dimensional subspace V12 for which span⟨uk,νk<d⟩⊂V12⊂span⟨uk,νk≤d⟩ and ‖sin∠(V12,Xext0)‖=1. Bind a basis of the d-dimensional subspace V12⊂R(n+d) into the (n+d)×d matrix Xˆ3ext, so span⟨Xˆ3ext⟩=V12. Again, by Proposition 7.9 for some matrix Δ, (Δ,Xˆ3ext) is a solution to (7) & (9). Then ‖sin∠(Xˆ3ext,Xext0)‖=1≥(1+‖X0‖2)−1/2. Then ‖sin∠(Xˆextmod,Xext0)‖≥(1+‖X0‖2)−1/2, which contradicts (59). Thus, the random event 3 occurs.
Now prove that the random event 2 occurs. Let Δ1 and Δ2 be two solutions to the optimization problem (7). Whenever the random event (59) occurs, the respective solutions Xˆ1 and Xˆ2 to equation (9) exist. By already proved uniqueness, they are equal, i.e., Xˆ1=Xˆ2. Then both Δ1 and Δ2 are solutions to the optimization problem
‖Δ(Σ1/2)†‖F→min;Δ(I−PΣ)=0;(C−Δ)Xˆ1ext=0
for the fixed Xˆ1ext=(Xˆ1−I)=(Xˆ2−I). By Proposition 7.2 and Remark 7.2-1, the least element in the optimization problem (28) for X=Xˆ1ext is attained for the unique matrix Δ=CXˆ1ext(Xˆ1ext⊤ΣXˆ1ext)†Xˆ1ext⊤Σ. Since it is attained, it is also attained for both Δ1 and Δ2. Hence, Δ1=Δ2. Thus, the random event 2 occurs.
We proved that the random event 1 always occurs, and the random events 2 and 3 occur whenever (59) occurs, which occurs either with high probability or eventually as desired. □
This uniqueness of the solution Δ to the optimization problem (7) agrees with the uniqueness result in [6]. The solution is unique if νd<νd+1.
1. In Theorem 4.1, the event 1 occurs always, not just with high probability or eventually. The solution Δ to (7) exists and also solves (11) due to Proposition 7.6. Thus, the first sentence of Theorem 4.2 is true. The second sentence of Theorem 4.2 has been already proved, since the constraints in the optimization problems (7) and (11) are the same.
2 & 3. The proof of consistency of the estimator defined with (11) & (9) and of the existence of the solution is similar to the proof for the estimator defined with (7) & (9) in Theorems 3.5–3.7 and 4.1. The only difference is skipping the use of Proposition 7.6. Notice that we do not prove the uniqueness of the solution because we cannot use Proposition 7.9. □
To Remark4.2-1. The amended Theorem 4.2 can be proved similarly. In the proof of part 1, read “The solution Δ to (7) … solves (12) due to Proposition 7.8.” In the proof of parts 2 and 3, read “The only difference is using Proposition 7.8, part 2 instead of Proposition 7.6.”
Proofs of auxiliary resultsProof of lemmas on perturbation bounds for invariant subspaces
For the proof of Lemma 6.5 itself, see parts 2 and 3 of the proof below. For the proof of Remark 6.5-1, see parts 2, 3 and 4 below. Part 1 is a mere discussion of why the conditions of Remark 6.5-1 are more general than ones of Lemma 6.5.
In the proof, we assume that {x:x⊤Bx>0}0\}$]]> is the domain of the function f(x). The assumption affects the definition of limx→x∗f(x), and inff is the infimum of f(x)over the domain.
1. At first, clarify the conditions of Remark 6.5-1. As it is, the existence of a point x such that
lim inft→→xf(t→)=inft→⊤Bt→>0f(t→)0}{\inf }f(\vec{t})\]]]>
is assumed in Remark 6.5-1. Now, prove that, under the preceding condition of Remark 6.5-1, there exists a vector x≠0 that satisfies (61).
The function f(x) is homogeneous of degree 0, i.e.,
f(kx)=f(x)ifk∈R∖{0}andx⊤Bx>0.0.\]]]>
Hence, all values which are attained by f(x) on its domain {x:x⊤Bx>0}0\}$]]>, are also attained on the bounded set {x:‖x‖=1,x⊤Bx>0}0\}$]]>:
f({x:‖x‖=1,x⊤Bx>0})=f({x:x⊤Bx>0}).0\big\}\big)=f\big(\big\{x:{x}^{\top }Bx>0\big\}\big).\]]]>
Then
inf‖x‖=1x⊤Bx>0f(x)=infx⊤Bx>0f(x).0\end{array}}{\inf }f(x)=\underset{{x}^{\top }Bx>0}{\inf }f(x).\]]]>
Let F be a closure of {x:‖x‖=1,x⊤Bx>0}0\}$]]>. There is a sequence {xk,k=1,2,…} such that ‖xk‖=1 and xk⊤Bxk>00$]]> for all k, and limk→∞f(xk)=infx⊤Bx>0f(x)0}}f(x)$]]>. Since F is a compact set, there exists x∗∈F which is a limit of some subsequence {xki,i=1,2,…} of {xk,k=1,2,…}. Then either
lim infx→x∗f(x)≤infx⊤Bx>0f(x)0}{\inf }f(x)\]]]>
or, if xki=x∗ for i large enough,
f(x∗)≤infx⊤Bx>0f(x).0}{\inf }f(x).\]]]>
(In equations (62) and (63), we assume that {x:x⊤Bx>0}0\}$]]> is a domain of f(x), so (63) implies x∗⊤Bx∗>00$]]>.) Again, due to the homogeneity, lim infx→x∗f(x)≤f(x∗) if f(x∗) makes sense. Hence (62) follows from (63) and thus holds true either way.
Taking the limit in the relation f(x)≥inff, we obtain the opposite inequality
lim infx→x∗f(x)≥infx⊤Bx>0f(x).0}{\inf }f(x).\]]]>
Thus, the equality (25) holds true for some x∗∈F. Note that ‖x∗‖=1, so x∗≠0.
2. Prove that under the conditions of Lemma 6.5 or Remark 6.5-1eitherf(x∗)≤f(x)orx∗⊤(A+A˜)x∗≤0.
Because the matrix B is symmetric and positive semidefinite, x⊤Bx=0 if and only if Bx=0, and x⊤Bx>00$]]> if and only if Bx≠0. As Bx0≠0, x0⊤Bx0>00$]]> and the function f(x) is well-defined at x0.
Under the conditions of Lemma 6.5 the function f(x) is well-defined at x0 and attains its minimum at x∗, so f(x∗)≤f(x0).
Under the conditions of Remark 6.5-1 we consider 3 cases concerning the value of x∗⊤Bx∗.
Case 1.x∗⊤Bx∗<0. But on the domain of f(x) the inequality x⊤Bx>00$]]> holds true. Since x∗ is a limit point of the domain of f(x), the inequality x∗⊤Bx∗≥0 holds true, and Case 1 is impossible.
Case 2.x∗⊤Bx∗=0. Prove that x∗⊤(A+A˜)x∗≤0. On the contrary, let x∗⊤(A+A˜)x∗>00$]]>. Remember once again that x⊤Bx>00$]]> on the domain of f(x). Then
limx→x∗f(x)=limx→x∗x⊤(A+A˜)xx⊤Bx=+∞,
which cannot be inff(x). The contradiction obtained implies that x∗⊤(A+A˜)x∗≤0.
Case 3.x∗⊤Bx∗>00$]]>. Then the function f(x) is well-defined at x∗, and
f(x∗)=limx→x∗f(x)=inff(x)≤f(x0).
So, f(x∗)≤f(x0) in Case 3.
3. Proof of Lemma 6.5 and proof of Remark 6.5-1 when f(x∗)≤f(x∗). Then
x⊤(A+A˜)xx⊤Bx≤x0⊤(A+A˜)x0x0⊤Bx0.
As Ax0=0,
x⊤Ax≤−x⊤A˜x+x0⊤A˜x0x⊤Bxx0⊤Bx0≤‖A˜‖(‖x‖2+‖x0‖2x⊤Bxx0⊤Bx0).
With use of eigendecomposition of A, the inequality x⊤Ax≥λ2(A)‖x‖2×sin2∠(x,x0) can be proved. Hence the desired inequality follows:
λ2(A)sin2∠(x,x0)≤‖A˜‖(1+‖x0‖2x0⊤Bx0·x⊤Bx‖x‖2).
4. Proof of Remark 6.5-1 when x∗⊤(A+A˜)x∗≤0. Then
x⊤Ax≤−x⊤A˜x,λ2(A)‖x‖2sin2∠(x,x0)≤‖A˜‖‖x‖2,λ2(A)sin2∠(x,x0)≤‖A˜‖,
whence the desired inequality follows. □
If A and B are symmetric matrices of the same size, and furthermore the matrix B is positive definite, denote
maxAB=λmax(B−1A).
The notation is used in the proof of Lemma 6.6.
Let1≤d1≤n,0≤d2≤n. LetX∈Rn×d1be a matrix of full rank, and V be ad2-dimensional subspace inRn. ThenmaxX⊤(I−PV)XX⊤X=‖sin∠(X,V)‖2ifd1≤d2,maxX⊤(I−PV)XX⊤X=1ifd1>d2.{d_{2}}.\end{aligned}\]]]>
Using the min-max theorem, the relation span⟨X⟩=span⟨Pspan⟨X⟩⟩ and simple properties of orthogonal projectors, construct the inequality
maxX⊤(I−PV)XX⊤X=maxv∈Rd1∖{0}v⊤X⊤(I−PV)Xvv⊤X⊤Xv=maxw∈span⟨X⟩∖{0}w⊤(I−PV)ww⊤w=maxv∈Rn∖{0}v⊤Pspan⟨X⟩(I−PV)Pspan⟨X⟩vv⊤Pspan⟨X⟩Pspan⟨X⟩v≥maxv∈Rn∖{0}v⊤Pspan⟨X⟩(I−PV)Pspan⟨X⟩vv⊤v=λmax(Pspan⟨X⟩(I−PV)Pspan⟨X⟩)=λmax(Pspan⟨X⟩(I−PV)(I−PV)Pspan⟨X⟩)=‖Pspan⟨X⟩(I−PV)‖2.
On the other hand,
maxw∈span⟨X⟩∖{0}w⊤(I−PV)ww⊤w=maxw∈span⟨X⟩∖{0}w⊤Pspan⟨X⟩(I−PV)Pspan⟨X⟩ww⊤w≤maxv∈Rn∖{0}v⊤Pspan⟨X⟩(I−PV)Pspan⟨X⟩vv⊤v.
Thus,
maxX⊤(I−PV)XX⊤X=‖Pspan⟨X⟩(I−PV)‖2.
If d1≤d2, then ‖Pspan⟨X⟩(I−PV)‖=‖sin∠(X,V)‖ due to (23). Otherwise, if d1>d2{d_{2}}$]]>, then
dimspan⟨X⟩+dimV⊥=rkX+n−dimV=d1+n−d2>n.n.\]]]>
Hence the subspaces span⟨X⟩ and V⊥ have nontrivial intersection, i.e., there exists w≠0, w∈span⟨X⟩∩V⊥. Then Pspan⟨X⟩(I−PV)w=w, whence ‖Pspan⟨X⟩(I−PV)‖≥1. On the other hand, ‖Pspan⟨X⟩(I−PV)‖≤‖Pspan⟨X⟩‖×‖(I−PV)‖≤1. Thus, ‖Pspan⟨X⟩(I−PV)‖=1. This completes the proof. □
The matrix B is positive semidefinite, the matrix X0⊤BX0 is positive definite, and the matrix X0 is of full rank d (hence, n≥d). The matrix A satisfies inequality A≥λd+1(A)(I−Pspan⟨X0⟩) in the Loewner order.
Let X be a point where the functional f(x) defined in (26) attains its minimum. Since X0⊤BX0 is positive definite, f(X0) makes sense. Thus, f(X)≤f(X0),
maxX⊤(A+A˜)XX⊤BX≤maxX0⊤(A+A˜)X0X0⊤BX0.
Using the relations
X⊤A˜X≥−‖A˜‖X⊤X,X0⊤A˜X0≤‖A˜‖X0⊤X0,X⊤BX≤‖B‖X⊤X,AX0=0,
we have
maxX⊤AX−‖A˜‖X⊤X‖B‖X⊤X≤max‖A˜‖X0⊤X0X0⊤BX0,1‖B‖·(maxX⊤AXX⊤X−‖A˜‖)≤‖A˜‖maxX0⊤X0X0⊤BX0.
Since A≥λd+1(A)(I−Pspan⟨X0⟩), by Lemma 8.2λd+1(A)‖sin∠(X,X0)‖2≤λd+1(A)maxX⊤(I−Pspan⟨X0⟩)X⊤X≤maxX⊤AXX⊤X.
Then the desired inequality follows from (64):
‖sin∠(X,X0)‖2≤‖A˜‖λd+1(A)(1+‖B‖maxX0⊤X0X0⊤BX0).
□
1. Split the matrix PX0−I⊥, which is an orthogonal projector along the column space of the matrix (X0−I), into four blocks:
I−PX0−I=PX0−I⊥=P1P2P2⊤P4.
Up to the end of the proof, P1 means the upper-left n×n block of the (n+p)×(n+p) matrix PX0−I⊥. Prove that λmin(P1)=11+‖X0‖2.
Let X0=UΣV⊤ be a singular value decomposition of the matrix X0 (here Σ is a diagonal n×d matrix, U and V are orthogonal matrices). Then
PX0−I⊥=I−X0−IX0−I⊤X0−I−1X0−I=U(I−Σ(Σ⊤Σ+1)−1Σ⊤)U⊤UΣ(Σ⊤Σ+I)−1V⊤V(Σ⊤Σ+I)−1Σ⊤U⊤V(I−(Σ⊤Σ+I)−1)V⊤.
The n×n matrix I−Σ(Σ⊤Σ+I)−1Σ⊤ is diagonal; its diagonal entries are 11+σi2(X0), i=1,…,n, where
σi(X0) is the i-th singular value of X0 if 1≤i≤min(n,d),
σi(X0)=0 if min(n,d)<i≤n.
Those diagonal entries comprise all the eigenvalues of P1;
λmin(P1)=11+σmax2(‖X0‖)=11+‖X0‖2.
2. Due to equation (23), the square of the largest of sines of canonical eigenvalues between the subspaces V1 and V2 is equal to
‖sin∠(V1,V2)‖2=maxv∈V1∖{0}v⊤PV2⊥v‖v‖2.
Hence for v∈V1, v≠0,
‖sin∠(V1,V2)‖2≥v⊤PV2⊥v‖v‖2.
3. Prove the first statement of Theorem 8.3 by contradiction. Suppose that the matrix B is singular. Then there exist f∈Rd∖{0} and u=Af∈Rn such that Bf=0 and
u0d×1=AfBf∈V1,
where V1⊂Rn+d is the column space of the matrix (AB). Asthe columns of the matrix (AB) are linearly independent, (u0)≠0. Then, by (66),
sin∠AB,X0−I2≥u0⊤PX0−I⊥u0‖(u0)‖2=u⊤P1u‖u‖2≥≥λmin(P1)=11+‖X0‖2,
which contradicts condition (65).
4. Prove inequality (67). (Later on we will show that the second statement of Theorem 8.3 follows from (67)). There exists such a vector f∈Rd∖{0} that ‖(AB−1+X0)f‖=‖AB−1+X0‖‖f‖. Denote
u=(AB−1+X0)f,z=ABB−1f=AB−1ff=u0−X0−If∈V1.
Since (X0⊤,−I)PX0−I⊥=0 and PX0−I⊥(X0−I)=0,
z⊤PX0−I⊥z=u0−X0−If⊤PX0−I⊥u0−X0−If=u0⊤PX0−I⊥u0=u⊤P1u≥‖u‖2λmin(P1)=‖AB−1+X0‖2‖f‖21+‖X0‖2.
Notice that z≠0 because B−1f≠0 and the columns of the matrix (AB) are linearly independent. Thus,
0<‖z‖2=‖AB−1f‖2+‖f2‖≤(1+‖AB−1‖2)‖f‖2.
By (66),
sin∠AB,X0−I2≥z⊤P(X0−I)⊥z‖z‖2≥‖AB−1+X0‖2(1+‖X0‖2)(1+‖AB−1‖2),sin∠AB,X0−I≥‖AB−1+X0‖1+‖X0‖21+(‖X0‖+‖AB−1+X0‖)2.
5. Prove that the second statement of Theorem 8.3 follows from (67). The function
s(δ):=δ1+‖X0‖21+(‖X0‖+δ)2
is strictly increasing on [0,+∞), with s(0)=0 and limδ→+∞s(δ)=11+‖X0‖2. Therefore, inequality (67) implies the implication:
if‖AB−1+X0‖>δ,thensin∠AB,X0−I>δ1+‖X0‖21+(‖X0‖+δ)2.\delta ,\\{} \text{then}\hspace{2.5pt}\left\| \sin \angle \left(\left(\begin{array}{c}A\\{} B\end{array}\right),\hspace{0.1667em}\left(\begin{array}{c}{X_{0}}\\{} -I\end{array}\right)\right)\right\| & >\frac{\delta }{\sqrt{1+\| {X_{0}}{\| }^{2}}\hspace{0.1667em}\sqrt{1+{(\| {X_{0}}\| +\delta )}^{2}}}.\end{aligned}\]]]>
The equivalent contrapositive implication is as follows:
ifsin∠AB,X0−I≤δ1+‖X0‖21+(‖X0‖+δ)2,then‖AB−1+X0‖≤δ.
The inverse function to s(δ) in (68) is
δ(s):=(1+‖X0‖2)(s2‖X0‖+s1−s2)1−(1+‖X0‖2)s2.
Substitute δ=δ(‖sin∠((ABsmallxxmat),(X0−I))‖) into (69) and obtain the following statement:
ifsin∠ABX0−I≤sin∠AB,X0−I,then‖AB−1+X0‖≤δ(‖sin∠((ABsmallxxmat),(X0−I))‖),
whence the second statement of Theorem 8.3 follows.
In part 5 of the proof, condition (65) is used twice. First, it is one of conditions of the first statement of the theorem: without it, the matrix B might be singular. Second, the function δ(s) is defined on interval [0,11+‖X0‖2). □
Let(X0−I)be an(n+d)×dmatrix, and let{(AmBm),AmBmm=1,2,…}be a sequence of(n+d)×dmatrices of rank d. If‖sin∠((AmBm),(X0−I))‖→0asm→∞, then:
the matrixBmis nonsingular for m large enough,
−AmBm−1→X0asm→∞.
Generalized eigenvalue problem for positive semidefinite matrices: proofs
For fixed i, split the matrix T in two blocks. Let T=[Ti1,Ti2], where Ti1 is the matrix constructed of the first i columns of T, and Ti2 is the matrix constructed of the last n−i+1 columns of T. Denote V1 and V2 the column spaces of the matrices Ti1 and Ti2, respectively. Then dimV1=i and dimV2=n−i+1.
1. The proof of the fact thatνi∈{λ≥0|“∃V,dimV=i:(A−λB)|V≤0”}ifνi<∞. In other words, if νi<∞, then relations
λ≥0,dim(V)=i,(A−λB)|V≤0
hold true for λ=νi and V=V1.
If v∈V1, then v=Ti1x for some x∈Ri. Hence
v⊤(A−νiB)v=x⊤Ti1⊤(A−νiB)Ti1x=x⊤diag(λ1−νiμ1,…,λi−νiμ1)x=∑j=1ixj2(λj−νiμj).
The inequality λj−νiμj≤0 holds true for all j such that either λj=μj=0 or λj/μj≤νi; particularly, it holds true for j=1,…,i. Hence v⊤(A−νiB)v≤0.
2. The proof of the fact thatνiis a lower bound of the set{λ≥0|“∃V,dimV=i:(A−λB)|V≤0”}. In other words, if there exists a subspace V⊂Rn such that the relations (70) hold true, then νi≤λ.
By contradiction, suppose that dimV=i, (A−λB)|V≤0, νi>λ≥0\lambda \ge 0$]]>. Then νi>00$]]>.
Now prove that (A−λB)|V2>00$]]>. If v∈V2∖{0}, then v=Ti2x for some x∈Rn−i+1∖{0}. Then
v⊤(A−λB)v=∑j=inxj+1−i2(λj−λμj).
For j≥i, due to the inequality νj≥νi>00$]]> and the conditions of the lemma, the case λj=0 is impossible; thus λj>00$]]>. Prove the inequality λj−λμj>00$]]>. If μj>00$]]>, then λj−λμj=(νj−λ)μj. Since νj≥νi>λ\lambda $]]>, the first factor νi−λ is a positive number. Hence, λj−λμj>00$]]>. Otherwise, if μj=0, then λj−λμj=λj>00$]]>. Thus the inequality λj−λμj>00$]]> holds true in both cases. Hence v⊤(A−λB)v>00$]]>. Since this holds for all v∈V2∖{0}, the restriction of the quadratic form A−λB onto the linear subspace V2 is positive definite.
On the one hand, since (A−λB)|V≤0 and (A−λB)|V2>00$]]>, the subspaces V and V2 have a trivial intersection. On the other hand, since dimV+dimV2=n+1>nn$]]>, the subspaces V and V2 cannot have a trivial intersection. We got a contradiction.
Hence νi≤λ, and νi is a lower bound of {λ≥0|“∃V,dimV=i:(A−λB)|V≤0”}. That completes the proof of Lemma 7.1. □
Remember that M† is the Moore–Penrose pseudoinverse matrix to M; span⟨M⟩ is the column span of the matrix M. If matrices M and N are compatible for multiplication, then span⟨MN⟩⊂span⟨M⟩. (Furthermore, span⟨M1⟩⊂span⟨M2⟩ if and only if M1=M2N for some matrix N). Hence, span⟨MM⊤⟩=span⟨M⟩ (to prove it, we can use the identity M=MM⊤(M⊤)†).
Since the n×n covariance matrix Σ is positive semidefinite, for every k×n matrix M the equality span⟨MΣM⊤⟩=span⟨MΣ⟩ holds true. This can be proved with use of the matrix square root.
If what follows, for a fixed (n+d)×d matrix X denote
Δpm=CX(X⊤ΣX)†X⊤Σ,
where C is an m×(n+d) matrix, Σ is an n×n positive semidefinite matrix.
1, necessity. Relation (30) is a necessary condition for compatibility of the constraints in (28). Let Δ(I−PΣ)=0 and (C−Δ)X=0 for some m×(n+d) matrix Δ. Due to Δ(I−PΣ)=0, Δ=MΣ for some matrix M. Then CX=ΔX=MΣX, X⊤C⊤=X⊤ΣM⊤, whence span(X⊤C⊤)⊂span(X⊤Σ).
1, sufficiency. Relation (30) is a sufficient condition for compatibility of the constraints in (28). Let span(X⊤C⊤)⊂span(X⊤Σ). Then X⊤C⊤=X⊤ΣM for some matrix M. The constraints Δ(I−PΣ)=0, (C−Δ)X=0 are satisfied for Δ=M⊤Σ, so they are compatible.
2a, eqns. (31). If the constraints are compatible, they are satisfied forΔ=Δpm. Indeed,
Δpm(I−PΣ)=CX(X⊤ΣX)†X⊤Σ(I−PΣ)=0,
since Σ(I−PΣ)=0. If the constraints are compatible, then
span(X⊤ΣX)=span(X⊤Σ)⊂span(X⊤C⊤),
whence
X⊤ΣX(X⊤ΣX)†X⊤C⊤=PX⊤ΣXX⊤C⊤=X⊤C⊤,ΔpmX=CX(X⊤ΣX)†X⊤ΣX=CX,(C−Δpm)X=0.
2a, eqn. (32) and 2b. If the constraints are compatible, then the constrained least element ofΔΣ†Δ⊤is attained forΔ=Δpm. The least element is equal toCX(X⊤ΣX)†X⊤C⊤. Let Δ satisfy the constraints, which imply ΔPΣ=Δ and ΔX=CX. Expand the product
(Δ−Δpm)Σ†(Δ−Δpm)⊤=ΔΣ†Δ⊤−ΔpmΣ†Δ⊤−ΔΣ†Δpm⊤+ΔpmΣ†Δpm⊤.
Simplify the expressions for three (of four) summands:
ΔΣ†Δpm⊤=ΔΣ†ΣX(X⊤ΣX)†X⊤C⊤=ΔPΣX(X⊤ΣX)†X⊤C⊤=ΔX(X⊤ΣX)†X⊤C⊤=CX(X⊤ΣX)†X⊤C⊤.
Applying matrix transposition to both sides of the last chain of equalities, we get
ΔpmΣ†Δ⊤=CX(X⊤ΣX)†X⊤C⊤.
For the last summand,
ΔpmΣ†Δpm⊤=CX(X⊤ΣX)†X⊤ΣΣ†ΣX(X⊤ΣX)†X⊤C⊤=CX(X⊤ΣX)†X⊤ΣX(X⊤ΣX)†X⊤C⊤=CX(X⊤ΣX)†X⊤C⊤.
Thus, (71) implies that
ΔΣ†Δ⊤=(Δ−Δpm)Σ†(Δ−Δpm)⊤+CX(X⊤ΣX)†X⊤C⊤.
Hence
ΔΣ†Δ⊤≥CX(X⊤ΣX)†X⊤C⊤,
and statement 2b of the theorem is proved. For Δ=Δpm, equality is attained, which coincides with (32).
Remark7.2-1. The least point is attained for a unique Δ. It is enough to show that if Δ satisfies the constraints and ΔΣ†Δ⊤=CX(X⊤ΣX)†X⊤C⊤, then Δ=Δpm.
Indeed, if Δ satisfies the constraints Δ(I−PΣ)=0 and (C−Δ)X=0, and ΔΣ†Δ⊤=CX(X⊤ΣX)†X⊤C⊤, then due to (72)
(Δ−Δpm)Σ†(Δ−Δpm)⊤=0.
As Σ† is a positive semidefinite matrix, (Δ−Δpm)Σ†=0 and (Δ−Δpm)PΣ=(Δ−Δpm)Σ†Σ=0. Add the equality Δ(I−PΣ)=0 (which is one of the constraints) and subtract the equality Δpm(I−PΣ)=0 (which is one of equalities (31) and holds true due part 2a of the theorem). Obtain
Δ−Δpm=(Δ−Δpm)PΣ+Δ(I−PΣ)−Δpm(I−PΣ)=0,
whence Δ=Δpm. □
1. Necessity. Since the matrices C⊤C and Σ are positive semidefinite, the matrix pencil ⟨C⊤C,Σ⟩ is definite if and only if the matrix C⊤C+Σ is positive semidefinite. Thus, if the matrix pencil ⟨C⊤C,Σ⟩ is definite, then the matrix C⊤C+Σ is positive definite. As the columns of the matrix X are linearly independent, the matrix X(C⊤C+Σ)X⊤=X⊤C⊤CX+X⊤ΣX is positive definite as well, whence span(X⊤C⊤CX+X⊤ΣX)=Rn.
If the constraints are compatible, then the condition (30) holds true, whence
Rn=span⟨X⊤C⊤CX+X⊤ΣX⟩⊂span⟨X⊤C⊤CX⟩+span⟨X⊤ΣX⟩=span⟨X⊤C⊤⟩+span⟨X⊤Σ⟩=span⟨X⊤Σ⟩=span⟨X⊤ΣX⟩.
Since span⟨X⊤ΣX⟩=Rn, the matrix X⊤ΣX is nonsingular.
2. Sufficiency. If the matrix X⊤ΣX is nonsingular, then
span⟨X⊤Σ⟩=span⟨X⊤ΣX⟩=Rn⊃span⟨X⊤C⊤⟩.
Thus the condition (30), which is the necessary and sufficient condition for compatibility of the constraints, holds true. □
Construct simultaneous diagonalization of matrices XCC⊤X⊤ and XΣX⊤ (according to Theorem 6.2) that satisfies Remark 6.2-2:
X⊤C⊤CX=(T−1)⊤ΛT−1,X⊤ΣX=(T−1)⊤MT−1.
Notations Λ, M, T=T1T2, μi, λi, νi are taken from Theorem 6.2, Remark 7.2-1, and Lemma 7.1.
The subspace
span⟨X⊤C⊤⟩=span⟨X⊤C⊤CX⟩=span⟨(T−1)⊤ΛT−1⟩=span⟨(T−1)⊤Λ⟩
is spanned by columns of the matrix (T−1)⊤ that correspond to nonzero λi’s. Similarly, the subspace span⟨X⊤Σ⟩=span⟨(T−1)⊤M⟩ is spanned by columns of the matrix (T−1)⊤ that correspond to non-zero μi’s. Note that the columns of the matrix (T−1)⊤ are linearly independent. The condition span⟨X⊤C⊤⟩⊂span⟨X⊤Σ⟩ is satisfied if and only if λi≠0 for all i such that μi≠0 (that is νi<∞, i=1,…,d, where notation νi=λi/νi comes from Theorem 6.2). Thus, due to Proposition 6.3,
(X⊤ΣX)†=TM†T⊤.
Construct the chain of equalities:
minΔ(I−PΣ)=0(C−Δ)X=0λk+m−d(ΔΣ†Δ⊤)=(a)λk+m−d(CX(X⊤ΣX)†X⊤C⊤)=λk+m−d(CXTM†T⊤X⊤C⊤)=(b)λk(M†T⊤X⊤C⊤CXT)=λk(M†Λ)=νk=(c)min{λ≥0:“∃V1⊂Rd,dimV1=k:(X⊤C⊤CX−λX⊤ΣX)|V1≤0”}=(d)min{λ≥0:“∃V⊂span⟨X⟩,dimV=k:(C⊤C−λΣ)|V≤0”}.
Equality (a) follows from 7.2 because the matrix CX(X⊤ΣX)†X⊤C⊤ is the least value of the expression ΔΣ†Δ⊤ with constraints (I−PΣ)Δ⊤=0 and (C−Δ)X=0.
Equality (b) follows from the relation between characteristic polynomials of two products of two rectangular matrices:
χCXTM†T⊤X⊤C⊤(λ)=(−λ)m−dχM†T⊤X⊤C⊤CXT(λ)
because CXT is an m×d matrix and M†T⊤X⊤C⊤ is a d×m matrix. Thus, the matrix CXTM†T⊤X⊤C⊤ has all the eigenvalues of the matrix M†T⊤X⊤C⊤×CXT=M†Λ and, besides them, the eigenvalue 0 of multiplicity m−d. All these eigenvalues are nonnegative.
Equality (c) holds true due to Lemma 7.1.
Since the columns of the matrix X are linearly independent, there is a one-to-one correspondence between subspaces of span⟨X⟩ and of Rd: if V is a subspace of span⟨X⟩, then there exists a unique subspace V1⊂Rd, and for those V and V1,
dimV=dimV1;
the restriction of the quadratic form C⊤C−λΣ to the subspace V is negative semidefinite if and only if the restriction of the quadratic form X⊤C⊤CX−λX⊤ΣX to the subspace V1 is negative semidefinite.
Hence, equality (d) holds true.
Equation (34) is proved. As to Remark 7.4-1, the minimum in the left-hand side of (34) is attained for Δ=Δpm. The minimum in the right-hand side of (34) is attained if the subspace V is a linear span of k columns of the matrix XT that correspond to the k least νi’s. □
By Lemma 7.1 and Proposition 7.4, the inequality (37) is equivalent to the obvious inequality
min{λ≥0:“∃V⊂span⟨X⟩,dimV=k:(C⊤C−λΣ)|V≤0”}≥min{λ≥0|“∃V,dimV=k:(A−λB)|V≤0”}.
From the proof it follows that if νd=∞, then for any (n+d)×d matrix X of rank d the constraints in (28) are not compatible.
Now prove that if νd<∞ and X=[u1,u2,…,ud], then the inequality in Proposition 7.5 becomes an equality. Indeed, then the constraints in (28) are compatible because they are satisfied for Δ=CTDT−1, where
D=diag(d1,d2,…,dd+n),dk=1ifμk>0andk≤d,0ifμk=0ork>d.0\hspace{2.5pt}\text{and}\hspace{2.5pt}k\le d,\\{} 0\hspace{1em}& \text{if}\hspace{2.5pt}{\mu _{k}}=0\hspace{2.5pt}\text{or}\hspace{2.5pt}k>d.\end{array}\right.\end{aligned}\]]]>
By Proposition 7.2minΔ(I−PΣ)=0(C−Δ)X=0λk+m−d(ΔΣ†Δ⊤)=λk+m−d(CX(X⊤ΣX)†X⊤C⊤)=λk((X⊤ΣX)†X⊤C⊤CX)=λk(Md†Λd)=νk,
where Md=diag(μ1,…,μd) and Λd=diag(λ1,…,λd) are principal submatrices of the matrices M and Λ, respectively. □
For every matrix Δ that satisfies the constraints (I−PΣ)Δ=0 and rk(C−Δ)≤n, there exists an (n+d)×d matrix X of rank d such that (C−Δ)X=0. Assuming that such Δ exists, we get ν<+∞ because the equalities ν=+∞, (I−PΣ)Δ=0, rkX=d, and (C−Δ)X=0 cannot hold simultaneously.
We have
‖Δ(Σ1/2)†‖F2=tr(ΔΣ†Δ⊤)=∑i=1mλi(ΔΣ†Δ⊤)=∑i=1m−dλi(ΔΣ†Δ⊤)+∑k=1dλk+m−d(Δ(Σ)†Δ⊤)≥0+∑k=1dνk,
where the inequalities hold true due to positive semidefiniteness of Σ and due to Proposition 7.5.
If νd=∞, than the constraints Δ(I−PΣ)=0 and rk(C−Δ)≤n are not compatible. Otherwise, the equality in (73) is attained for Δ=Δem:=CX(X⊤ΣX)†×X⊤Σ, where the matrix X consists of first d rows of the matrix T, where T comes from decomposition (35).
Thus, if the constraints in (7) are compatible, then the minimum is equal to (∑k=1dνk)1/2 and is attained at Δem. Otherwise, if the constraints are incompatible, then by contraposition to the second statement of Proposition 7.5νd=+∞ and (∑k=1dνk)1/2=+∞.
If the minimum in (7) is attained at Δ, then the inequality (73) becomes an equality, whence λi(ΔΣ†Δ⊤)=0,i=1,…,m−d;λk+m−d(ΔΣ†Δ⊤)=νk,k=1,…,d; in particular,
λmax(ΔΣ†Δ⊤)=νd.
Remember that νd is the minimum value in (11). Thus, the minimum in (11) is attained at Δ, although it may be also attained elsewhere. □
1. The monotonicity follows from results of [14]. The unitarily invariant norm is a symmetric gauge function of the singular values, and the symmetric gauge function is monotonous in non-negative inputs (see [14, ineq. (2.5)]).
2. Let σ1(M1)<σ1(M2) and σi(M1)≤σi(M2) for all i=2,…,min(m,n). Then for all k=1,…,min(m,n)∑i=1kσi(M1)≤σ1(M1)+σ2(M1)+⋯+σmin(m,n)(M1)σ1(M2)+σ2(M1)+⋯+σmin(m,n)(M1)∑i=1kσi(M2).
Due to Ky Fan [3, Theorem 4] or [14, Theorem 1], this implies that
‖M1‖U≤σ1(M1)+σ2(M1)+⋯+σmin(m,n)(M1)σ1(M2)+σ2(M1)+⋯+σmin(m,n)(M1)‖M2‖U.
Since
0≤σ1(M1)+σ2(M1)+⋯+σmin(m,n)(M1)σ1(M2)+σ2(M1)+⋯+σmin(m,n)(M1)<1and‖M2‖U>0,0,\]]]>‖M1‖U<‖M2‖U. □
Notice that the optimization problems (7), (11), and (12) have the same constraints. If the constraints are compatible, then the minimum in (7) is attained for Δ=Δem:=CX(X⊤ΣX)†X⊤Σ.
1. Let Δmin(7) minimize (7), and let Δfeas satisfy the constraints. Then, by Proposition 7.5 and eqn. (75),
λk+m−d(Δmin(7)Σ†Δmin(7)⊤)=νk≤λk+m−d(ΔfeasΣ†Δfeas⊤),k=1,…,d;σd+1−k(Δmin(7)(Σ1/2)†)≤σd+1−k(Δfeas(Σ1/2)†),k=max(1,d+1−m),…,d;σj(Δmin(7)(Σ1/2)†)≤σj(Δfeas(Σ1/2)†),j=1,…,min(d,m);
by eqn. (74)
λi(Δmin(7)Σ†Δmin(7)⊤)=0,i=1,…,m−d,σm+1−i(Δmin(7)(Σ1/2)†)=0≤σm+1−i(Δfeas(Σ1/2)†),i≤m−d;σj(Δmin(7)(Σ1/2)†)=0≤σj(Δfeas(Σ1/2)†),d+1≤j≤min(m,n+d).
Thus
σj(Δmin(7)(Σ1/2)†)≤σj(Δfeas(Σ1/2)†)for allj≤min(m,n+d),
whence by Proposition 7.7‖Δmin(7)(Σ1/2)†‖U≤‖Δfeas(Σ1/2)†‖U. Thus Δmin(7) indeed minimizes (12).
2. Let Δmin(12) minimize (12), so the constraints are compatible. Then Δem minimizes both (7) and (11), see Proposition 7.6. Thus,
‖Δmin(12)(Σ1/2)†‖U≤‖Δem(Σ1/2)†‖U,
and by (76)
σj(Δem(Σ1/2)†)≤σj(Δmin(12)(Σ1/2)†)for allj≤min(m,n+d).
Then by Proposition 7.7 (contraposition to part 2)
σ1(Δem(Σ1/2)†)=σ1(Δmin(12)(Σ1/2)†),minΔ(I−PΣ)=0rk(C−Δ)≤n(ΔΣ†Δ⊤)=λmax(ΔemΣ†Δem⊤)=λmax(Δmin(12)Σ†Δmin(12)⊤).
Thus Δmin(12) indeed minimizes (11). □
We can assume that μi∈{0,1} in (35).
The set of matrices Δ that satisfy (8) depends only on span⟨Xˆext⟩ and does not change after linear transformations of columns of Xˆext.
By linear transformations of the columns, the matrix T−1Xˆext can be transformed to the reduced column echelon form. Thus, there exists such an (n+d)×d matrix T5 in the column echelon form that
span⟨Xˆext⟩=span⟨TT5⟩.
Notice that rkT5=rkXˆext=d.
Denote by d∗ and d∗ the first and the last of the indices i such that νi=νd. Then
νd∗−1<νd∗ifd∗≥2;νd∗=⋯=νd=⋯=νd∗;νd∗<νd∗+1ifd∗<n+d.
Necessity. Let Δ be a point where the constrained minimum in (7) is attained. Then equalities (74)–(75) from the proof of Proposition 7.6 hold true. Thus, due to Propositions 7.4 and 7.5, for all k=1,…,dmin{λ≥0:“∃V⊂span⟨Xˆext⟩,dimV=k:(C⊤C−λΣ)|V≤0”}=νk.
According to 7.4-1, we can construct a stack of subspaces
V1⊂V2⊂⋯⊂Vd=span⟨Xˆext⟩,
such that dimVk=k and the restriction of the quadratic form C⊤C−νkΣ to the subspace Vk is negative semidefinite, for all k≤d.
Now, prove that
span⟨ui:νi<νd⟩⊂span⟨Xˆext⟩.
Suppose the contrary: span⟨ui:νi<νd⟩⊄span⟨Xˆext⟩. Then there exists i<d∗ such that ui∉span⟨Xˆext⟩, and, as a consequence, ui∉Vmax{j:νj≤νi}. Find the least k such that uk∉Vmax{j:νj≤νk}. Let k∗ and k∗ denote the first and the last indices i such that νi=νk. Then 1≤k∗≤k≤k∗<d∗≤d≤d∗ and uk∉Vk∗.
Since span⟨u1,…,uk∗−1⟩⊂Vk∗−1⊂Vk∗,
dim(Vk∗∩span⟨uk∗,…,un+d⟩)=dim(Vk∗/span⟨u1,…,uk∗−1⟩)=dimVk∗−(k∗−1)=k∗−k∗+1.
Since uk∉Vk∗, uk∉Vk∗∩span⟨uk∗,…,un+d⟩,
dimspan⟨Vk∗∩span⟨uk∗,…un+d⟩,uk⟩=k∗−k∗+2.
Now, consider the (n+d−k∗+1)×(n+d−k∗+1) diagonal matrix
D(λ):=[uk∗,…,un+d]⊤(C⊤C−λΣ)[uk∗,…,un+d]=diag(λj−λμj,j=k∗,…,n+d)
for various λ. For λ=νk=νk∗, the inequality λj−νkμj≥0 holds true for all j≥k∗, so the matrix D(νk) is positive semidefinite. For λ=νk∗+1, the inequality λj−νk∗+1μj≤0 holds true for all k∗≤j≤k∗+1, so there exists a k∗−k∗+2-dimensional subspace of Rn+d−k∗+1 where the quadratic form D(νk∗+1) is negative semidefinite. For λ<νk∗+1, the inequality λj−λμj>00$]]> holds true for all k∗+1≤j≤n+d. Therefore, there exists an n+d−k∗-dimensional subspace of Rn+d−k∗+1 where the quadratic form D(λ) is positive definite. According to the proof of Sylvester’s law of inertia, there is no subspace of dimension k∗−k∗+2=(n+d−k∗+1)−(n+d−k∗)+1 where the quadratic form D(λ) is negative semidefinite. Thus, νk∗+1 is the least number such that there exists a k∗−k∗+2-dimensional subspace where the quadratic form D(λ) is negative semidefinite.
Similarly to the chain of equalities in the proof of Proposition 7.4,
νk∗+1=min{λ≥0:“∃V1,dimV1=k∗−k∗+2:D(λ)|V1≤0”}=min{λ≥0:“∃V1,dimV1=k∗−k∗+2:[uk∗,…,un+d]⊤(C⊤C−λΣ)[uk∗,…,un+d]|V1≤0”}=min{λ≥0:“∃V1,V⊂span⟨uk∗,…,un+d⟩,dimV=k∗−k∗+2:(C⊤C−λΣ)|V≤0”}
The restriction of the quadratic form C⊤C−νkΣ to the subspace span⟨uk∗,…,un+d⟩ is positive semidefinite because [uk∗,…,un+d]⊤(C⊤C−νkΣ)×[uk∗,…,un+d]=D(νk) is a positive semidefinite diagonal matrix. Then
{v∈span⟨uk∗,…un+d⟩:v⊤(C⊤C−νkΣ)v≤0}={v∈span⟨uk∗,…,un+d⟩:(C⊤C−νkΣ)v=0}
is a linear subspace. Since this subspace contains the subspace Vk∩span⟨uk∗,…,un+d⟩ (as the quadratic form C⊤C−νkΣ is negative semidefinite on Vk) and the vector uk (as uk∈span⟨uk∗,…,un+d⟩ and uk⊤(C⊤C−νkΣ)uk=λk−νkμk=0), it contains span⟨Vk∗∩span⟨uk∗,…,un+d⟩,uk⟩. But, as νk<νk∗+1, this contradicts (78).
Now, prove that
span⟨Xˆext⟩⊂span⟨ui:νi≤νd⟩.
Due to (77),
span⟨Xˆext⟩=span⟨span⟨Xˆext⟩∩span⟨ud∗,…,un+d⟩,u1,…,ud∗−1⟩.
Hence, to prove (80), it is enough to show that
span⟨Xˆext⟩∩span⟨ud∗,…,νn+d⟩⊂span⟨ud∗,…,νd∗⟩.
The restriction of the quadratic form C⊤C−νdΣ to the subspace span⟨ud∗,…,un+d⟩ is positive semidefinite. Hence
{v∈span⟨ud∗,…un+d⟩:v⊤(C⊤C−νdΣ)v≤0}={v∈span⟨ud∗,…un+d⟩:v⊤(C⊤C−νdΣ)v=0}
is a linear subspace (see equation (79)). This subspace contains the subspaces span⟨Xˆext⟩∩span⟨ud∗,…,νn+d⟩ and span⟨ud∗,…,νd∗⟩. Denote the dimension of the subspace (82):
d2=dim{v∈span⟨ud∗,…un+d⟩:v⊤(C⊤C−νdΣ)v=0}.
If (81) does not hold, then d2>d∗−d∗+1{d}^{\ast }-{d_{\ast }}+1$]]>; d2≥d∗−d∗+2. Then
∃V⊂span⟨ud∗,…un+d⟩,dimV=d2:(C⊤C−νdΣ)|V≤0
(as an instance of such a subspace V, we can take the one defined in (82)). Then, taking a d∗−d∗+2-dimensional subspace of V, we get
∃V⊂span⟨ud∗,…un+d⟩,dimV=d∗−d∗+2:(C⊤C−νdΣ)|V≤0.
Due to (78) (for k=d), νd∗+1≤νd, which does not hold true.
Assuming the contrary to (81), we got a contradiction. Hence, (81) and (80) hold true.
Sufficiency. Remember that T=[u1,…,un+d] is an (n+d)×(n+d) matrix of generalized eigenvectors of the matrix pencil ⟨C⊤C,Σ⟩, and respective generalized eigenvalues are arranged in ascending order. By means of linear operations of the columns, the matrix T−1Xˆext can be transformed into the reduced column echelon form. In other words, there exists such an n×n nonsingular matrix T8, that the (n+d)×n matrix
T5=T−1XˆextT8
is in the reduced column echelon form. The equality (83) implies that
span⟨Xˆext⟩=span⟨TT5⟩.
If condition (37) holds, then in representation (84) the matrix T5 has the following block structure
where T61 is a (d∗−d∗+1)×(d−d∗+1) reduced column echelon matrix. (Any of the blocks except T61 may be an “empty matrix”.)
Since the columns of T5 are linearly independent, the columns of T61 are linearly independent as well. Hence the matrix T61 may be appended with columns such that the resulting matrix T6=[T61,T62] is nonsingular. Perform the Gram–Schmidt orthogonalization of columns of the matrix T6 by constructing such an upper-triangular matrix
that T7⊤T6⊤T6T7=Id∗−d∗+1.
Change the basis in the simultaneous diagonalization of the matrices C⊤C and Σ. Denote
Tnew=[u1,…ud∗−1,[ud∗,…ud∗]T6T7,ud∗+1,…un+d].
If νd>00$]]>, the equation (35) with Tnew substituted for T holds true, since
Tnew⊤C⊤CTnew=Λ,Tnew⊤ΣTnew=M.
(Here we use that λd∗=⋯=λd∗, μd∗=⋯=μd∗. If νd=0, then the latter equation may or may not hold true.) The subspace
span⟨Xˆext⟩=span⟨TT5⟩=span⟨u1,…ud∗−1,[ud∗,…ud∗]T61⟩=span⟨u1,…ud∗−1,[ud∗,…ud∗]T61T71⟩
is spanned by the first d columns of the matrix Tnew.
It can be easily verified that span⟨Xˆext⊤C⊤⟩=span⟨T8⊤T5⊤Λ⟩ and span⟨Xˆext⊤Σ⟩=span⟨T8⊤T5⊤M⟩. The condition span⟨Xˆext⊤C⊤⟩⊂span⟨Xˆext⊤Σ⟩ holds true if (and only if) νd<∞. Thus, due to Proposition 7.2, if the condition νd<∞ holds true, then the constraints Δ(I−PΣ)=0 and (C−Δ)Xˆext=0 are compatible.
Let Δpm be a common point of minimum in
λk+m−d(ΔpmΣ†Δpm⊤)=minΔ(I−PΣ)=0(C−Δ)Xˆext=0λk+m−d(ΔΣ†Δ⊤)
for all k=1,…,d, such that Δpm(I−PΣ)=0 and (C−Δpm)Xˆext=0; such Δpm exists due to Remark 7.4-1. By Proposition 7.5,
λk+m−d(ΔpmΣ†Δpm⊤)=νk,k=1,…,d,
and, from the proof of Preposition 7.6,
λi(ΔpmΣ†Δpm⊤)=0,i=1,…,m−d.
The minimum in (7) is attained at Δ=Δpm.
The case νd=0 is trivial: then (37) imply that CXˆext=0. Then Δ=0 satisfies the constraints Δ(I−PΣ)=0 and (C−Δ)Xˆext=0 and minimizes the criterion function in (7). □
Remember that if νd<∞, then the constraints in (11) are compatible, and the minimum is attained and is equal to νd; see Proposition 7.5. Otherwise, if νd=∞, then the constraints in (11) are incompatible.
Transform the expression for the functional (38):
Q1(X):=λmax((X⊤ΣX)−1X⊤C⊤CX)=λmax(CX(X⊤ΣX)−1X⊤C⊤)=minΔ1∈Rm×(n+d):Δ1(I−PΣ)=0,(C−Δ1)X=0λmax(Δ1Σ†Δ1⊤).
Here we used the rule how eigenvalues of the matrix product change when the matrices are swapped, and we also used Propositions 7.2 and 7.3. By Proposition 7.5, Q1(X)≥νd.
If the minimum in (11) & (8) is attained (say at some point (Δ,Xˆext)), then the constraints in the right-hand side of (85) are compatible for X=Xˆext (particularly, Δ is a matrix that satisfies the constraints). Then by Proposition 7.3 the matrix Xˆext⊤ΣXˆext is nonsingular. Thus, for X=Xˆext, minimum in the right-hand of (85) is attained at Δ1=Δ (because Δ satisfies stronger constraints of (85) and brings a minimum to the same functional with weaker constraints of (11)).
Hence,
Q1(Xˆext):=minΔ1∈Rm×(n+d):Δ1(I−PΣ)=0,(C−Δ1)Xˆext=0λmax(Δ1Σ†Δ1⊤)=(ΔΣ†Δ⊤)=νd,
which is the minimum value of Q1.
Transform the expression for the functional (39):
λmax((X⊤ΣX)−1X⊤(C⊤C−mΣ)X)=λmax((X⊤ΣX)−1X⊤(C⊤C)X−mIn+d)=Q1(X)−m.
Hence, the functionals (38) and (39) attain their minimal values at the same points. □
Conclusion
The linear errors-in-variables model is considered. The errors are assumed to have the same covariance matrix for each observation and to be independent between different observations, however some variables may be observed without errors. Detailed proofs of the consistency theorems for the TLS estimator, which were first stated in [18], are presented.
It is proved that that the final estimator Xˆ for explicit-notation regression coefficients (i.e., for X0 in (1) or (2), and not the estimator Xˆext for Xext0 in equation (3), which sets the relationship between the regressors and response variables implicitly) is unique, either with high probability or eventually. This means that in the classification used in [8], the TLS problem is of 1st class set F1 (the solution is unique and “generic”), with high probability or eventually.
As by-product, we get that if in the definition of the estimator the Frobenius norm is replaced by the spectral norm, then the consistency theorems still hold true. The disadvantage of using spectral norm is that the estimator Xˆ is not unique then. (The set of solutions to the minimal spectral norm problem contains the set of solutions to the TLS problem. On the other hand, it is possible that the minimal spectral norm problem has solutions, but the TLS problem has not – this is the TLS problem of 1st class set F3; the probability of this random event tends to 0.)
Results can be generalized to any unitary invariant matrix norm. I do not know whether they hold true for non-invariant norms such as the maximum absolute entry, which is studied in [7].
ReferencesCheng, C.-L., Van Ness, J.W.: Statistical Regression with Measurement Error. Wiley (2010). MR1719513de Leeuw, J.: Generalized eigenvalue problems with positive semi-definite matrices. Psychometrika47(1), 87–93 (1982). MR0668507. https://doi.org/10.1007/BF02293853Fan, K.: Maximum properties and inequalities for the eigenvalues of completely continuous operators. Proceedings of the National Academy of Sciences of the USA37(11), 760–766 (1951). MR0045952. https://doi.org/10.1073/pnas.37.11.760Gallo, P.P.: Consistency of regression estimates when some variables are subject to error. Communications in Statistics – Theory and Methods11(9), 973–983 (1982). https://doi.org/10.1080/03610928208828287Gleser, L.J.: Estimation in a multivariate “errors in variables” regression model: Large sample results. The Annals of Statistics9(1), 24–44 (1981). MR0600530Golub, G.H., Hoffman, A., Stewart, G.W.: A generalization of the Eckart–Young–Mirsky matrix approximation theorem. Linear Algebra and its Applications88–89(Supplement C), 317–327 (1987). MR0882452. https://doi.org/10.1016/0024-3795(87)90114-5Hladík, M., Černý, M., Antoch, J.: EIV regression with bounded errors in data: total ‘least squares’ with Chebyshev norm. Statistical Papers (2017). https://doi.org/10.1007/s00362-017-0939-zHnětynková, I., Plešinger, M., Sima, D.M., Strakoš, Z., Van Huffel, S.: The total least squares problem in AX≈B: A new classification with the relationship to the classical works. SIAM Journal on Matrix Analysis and Applications32(3), 748–770 (2011). MR2825323. https://doi.org/10.1137/100813348Kukush, A., Markovsky, I., Van Huffel, S.: Consistency of the structured total least squares estimator in a multivariate errors-in-variables model. Journal of Statistical Planning and Inference133(2), 315–358 (2005). MR2194481. https://doi.org/10.1016/j.jspi.2003.12.020Kukush, A., Van Huffel, S.: Consistency of elementwise-weighted total least squares estimator in a multivariate errors-in-variables model AX=B. Metrika59(1), 75–97 (2004). MR2043433. https://doi.org/10.1007/s001840300272Marcinkiewicz, J., Zygmund, A.: Sur les fonctions indépendantes. Fundamenta Mathematicae29, 60–90 (1937). MR0115885Markovsky, I., Sima, D.M., Van Huffel, S.: Total least squares methods. Wiley Interdisciplinary Reviews: Computational Statistics2(2), 212–217 (2010). https://doi.org/10.1002/wics.65Markovsky, I., Willems, J.C., Van Huffel, S., De Moor, B.: Exact and Approximate Modeling of Linear Systems: A Behavioral Approach. SIAM, Philadelphia (2006). MR2207544. https://doi.org/10.1137/1.9780898718263Mirsky, L.: Symmetric gauge functions and unitarily invariant norms. The Quarterly Journal of Mathematics11(1), 50–59 (1960). MR0114821. https://doi.org/10.1093/qmath/11.1.50Newcomb, R.W.: On the simultaneous diagonalization of two semi-definite matrices. Quarterly of Applied Mathematics19(2), 144–146 (1961). MR0124336. https://doi.org/10.1090/qam/124336Petrov, V.V.: Limit Theorems of Probability Theory: Sequences of Independent Random Variables. Clarendon Press, Oxford (1995). MR1353441Pfanzagl, J.: On the measurability and consistency of minimum contrast estimates. Metrika14, 249–272 (1969). https://doi.org/10.1007/BF02613654Shklyar, S.V.: Conditions for the consistency of the total least squares estimator in an errors-in-variables linear regression model. Theory of Probability and Mathematical Statistics83, 175–190 (2011). MR2768857. https://doi.org/10.1090/S0094-9000-2012-00850-8Stewart, G., Sun, J.-g.: Matrix Perturbation Theory. Academic Press, San Diego (1990). MR1061154Van Huffel, S., Vandewalle, J.: The Total Least Squares Problem: Computational Aspects and Analysis. SIAM, Philadelphia (1991). MR1118607. https://doi.org/10.1137/1.9781611971002