# A Note on a Lower Bound on the Minimum Rank of a Positive Semidefinite Hankel Matrix Rank Minimization Problem

Authors: Yi Xu; Xiaorong Ren; Xihong Yan
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

This paper investigates the problem of approximating the global minimum of a positive semidefinite Hankel matrix minimization problem with linear constraints. We provide a lower bound on the objective of minimizing the rank of the Hankel matrix in the problem based on conclusions from nonnegative polynomials, semi-infinite programming, and the dual theorem. We prove that the lower bound is almost half of the number of linear constraints of the optimization problem.


---

## Body

## 1. Introduction

The matrix rank minimization problem, or minimizing the rank of a matrix subject to linear constraints, recently has gained tremendous popularity due to wide applications in various fields including machine learning [1], compressed sensing [2, 3], system identification and control [4, 5], and computer vision [6]. This problem can be formulated as the following program:(1)minrX,s.t.AX=b,where X∈ℝm×n is the optimization variable, rX is the rank of X, A:ℝm×n⟶ℝp is a linear map, and b∈ℝp. A special case of this problem is the matrix completion problem [2], recovering an unknown low-rank matrix from a sampling of its entries. For this special case, the constraints are simply a subset of the entries of the matrix. The majority of existing work on algorithms for problem (1) has concentrated on this special case. Many papers addressed methods to solve the matrix completion problem, for instance, the singular value thresholding algorithm [7], the accelerated proximal gradient algorithm [8], the matrix factorization-based approach [9], and the facial reduction [10–12]. Various other methods are well documented in [13–15] and references therein.In many engineering and statistical applications, for example, dynamical systems problems [16] and time-domain signal problems [17], the recovered matrix of problem (1), in addition to being low-rank, is required to have a Hankel structure. Driven by the wide applicability of the Hankel matrix minimization problem, there have been several algorithms available for solving it. Based on the nuclear norm model which minimizes the nuclear norm of the matrix instead of its rank, Fazel et al. [4] discussed several first-order algorithms for solving the structured rank minimization problem, including gradient projection methods, proximal point algorithms, and alternating direction methods of multipliers. Several evolutionary algorithms were proposed by Cai, including an iterative hard thresholding algorithm based on the nuclear norm model [18], an alternating direction method of multipliers based on Vandermonde factorization of a Hankel matrix model [19], and a projected Wirtinger gradient algorithm [20]. The major drawbacks of these methods are that the solutions obtained are not guaranteed to be a good approximate global solution for the problem since there have been no approximation bounds developed for these methods. Moreover, they are highly sensitive to some parameters which depend on a guess of the rank of the concerned matrix. Hence, in view of improving performance of algorithms for solving the problem, it is important to find an approximation for the rank of the optimal Hankel matrix. Along this direction, in this paper, we provide a lower bound on the minimum rank of a positive semidefinite Hankel matrix minimization problem with linear constraints, which is modeled as the following program:(2)minrX,AX=b,s.t.X≽0,Xis Hankel.Note that the positive semidefinite Hankel matrix completion problem is a special case of problem (2).Most literature about estimation of the rank of a matrix concentrates on the rank of the optimal matrix of a positive semidefinite program [21–24] or a band matrix [25–28]. Though the minimum rank of problem (2) is guaranteed theoretically through these methods from the previous work, they are not efficient since the structure emerging from a positive semidefinite Hankel matrix is not completely utilized. To our knowledge, this work is one of the first efforts to address the lower bound of the objective value of the positive semidefinite Hankel matrix rank minimization problem. We first construct a semidefinite program to describe the feasible region of problem (2); then derive an equivalent semi-infinite program for the dual of the semidefinite program using a conclusion from nonnegative polynomials; and finally, by the optimality conditions for the semi-infinite problem, we prove that a lower bound for the minimum objective of problem (2) is almost half of the number of its constraints.The remainder of the paper is organized as follows. Section2 summarizes some notations and preliminaries that serve as fundamentals of analysis. In Section 3, a detailed stepwise analysis is shown to convert our problem into a semi-infinite program. Moreover, we establish the main results under some mild assumptions. Finally, we conclude this paper in Section 4.


## 2. Preliminaries

In this section, we introduce some notations and basic definitions which will be used in the remaining part of the paper and some lemmas that serves as fundamentals to recast a positive semidefinite system as an equivalent semi-infinite program.Notations. Let ℝn be the n-dimensional Euclidean space and ℝm×n be the set of m×n real matrices. rX and TrX denote the rank and trace of a matrix X, respectively. A matrix X is symmetric positive definite (resp., positive semidefinite) and is denoted by X≻0 (resp., X≽0). xj represents the j-th component of vector x, and Xi,j represents the i,j entry of matrix X. Δ is the number of elements of set Δ. The symbol T represents the transpose. I represents the identity matrix. Pn is the set consisting of the polynomials with coefficients in ℝ and degree at most n. An n-degree polynomial pnt∈Pn: ℝn⟶ℝ is written as ∑i=0nαixi. Denote coefficients of polynomial pnt by pn=α0,α1,…,αnT∈ℝn+1. pt≥0 means pt is a nonnegative polynomial. Considering a collection of matrices C=Ckk=1m, where Ck∈ℝn×n, we write(3)CTx=∑k=1mCkxk,resp.CX=TrCkXk=1m,for the operations between a collection of matrices and a vector (resp., a matrix), where x∈ℝm and X∈ℝn×n. Let ℋ be a base of the n×n Hankel matrix space, which is defined as follows:(4)ℋ=Hkk=12n−1,whereHki,j=1i+j=k+10else,k=1,2,…,2n−1.Definition 1.
Ann×n real Hankel matrix is a matrix of the form:(5)x1x2⋯xn−1xnx2x3⋯xnxn+1⋮⋮⋮⋮⋮xn−1xn⋯x2n−3x2n−2xnxn+1⋯x2n−2x2n−1,where x1,…,x2n−1∈ℝ. It is obvious that an n×n Hankel matrix could be completely determined by its last row and first column, a total of 2n−1 entries. Let x:=x1,…,x2n−1T∈ℝ2n−1. The Hankel matrix can be constructed by vector x and can be expressed uniquely as ℋTx based on (3) and (4). Thus, program (2) can be rewritten as follows:(6)minx∈R2n−1rℋx,s.t.Ax=b,ℋTx≽0,where A=ak,j∈ℝp×2n−1.
Problem (6) is a special case of the matrix rank minimization problem (1) due to the special structure of the positive semidefinite Hankel matrix. However, the additional positive semidefinite Hankel structure requirement comes at a price, with theoretical and practical difficulties involved in the process of solving such a problem. Hence, we present some lemmas to provide tools to simplify the high technical requirement.Lemma 1.
(see [29]). Suppose that pt∈P2n and pt≥0,t∈ℝ. Then, pt is a sum of squares, that is,(7)pt=∑i=1sqi2t,where qit∈Pn.
We are now ready to state a lemma, which accords us with a mechanism to transform a semidefinite positive system to a nonnegative polynomial, which is the most useful part of our main result.Lemma 2.
Supposept∈P2n−2,t∈ℝ and p is the associated coefficient vector. Then, the following statements are equivalent:(a)
pt≥0(b)
There exists a matrixX∈ℝn×n such that(8)ℋX=p,X≽0,where ℋ is defined in (4)Proof.
Becausept∈P2n−2 and pt≥0, according to Lemma 1, we have(9)pt=∑i=1sqi2t,where qit∈Pn−1.
Letβ2n−1=1,t,…,t2n−2T∈ℝ2n−1 and βn=1,t,…,tn−1T∈ℝn, then pt=pβ2n−1 and qit=qiTβn,i=1,2,…,s, which means that(10)pt=pβ2n−1=∑i=1sβnTqiqiTβn=βnT∑i=1sqiqiTβn.
DefineX=∑i=1nqiqiT≽0; then,(11)pβ2n−1=βnTXβn.
Based on the equivalence of the coefficients ofti on the two sides of the above equation, we obtain ℋX=p and complete the proof in one direction.
For the other directions, sinceX≽0, X=∑i=1sqiqiT (s is the rank of X), which together with ℋX=p, it implies that(12)pt=pβ2n−1=ℋXβ2n−1=∑i=1sβnTqiqiTβn=βnT∑i=1sqiqiTβn=βnTXβn≥0.The following lemma, which can be obtained from ([21], Theorem 2), provides us a useful property of the optimal matrix of program (6).Lemma 3.
LetKn be the cone of positive semidefinite n×n matrices and ℬ be an affine subspace of the space of symmetric matrices such that the intersection Kn∩ℬ is nonempty and bounded. If codim ℬ=l+2l+1/2, where 1≤l≤n−2, then there is a matrix X∈Kn∩ℬ such that rX≤l.


## 3. A Lower Bound on the Optimal Objective of a Positive Seimdefinite Hankel Rank Minimization Problem

In this section, we investigate a lower bound on the minimum rank of problem (5). Beginning with a lemma, we first explore an important property of the optimal value of problem (6).Lemma 4.
The objective value of problem (6) is small than n.Proof.
An equivalent formulation for program (2) is stated as follows:(13)minrX,s.t.AX=b,Xi,k−i=Xi+1,k−i−1=⋯=Xk/2,k−k/2,i=1,…,n−1,k=2,…,n+1,X≽0,where · represents the floor function. It is clear that the affine subspace of the above program, denoted by ℬ, can be expressed by the following system:(14)AX=b,Xi,k−i=Xi+1,k−i−1=⋯=Xk/2,k−k/2,i=1,…,n−1,k=2,…,n+1.
It is evident that codimℬ=n−2n−1/2+p, which means(15)l=n−2n−12+p+14−32,where l is as defined in Lemma 3. A direct application of the statement of Lemma 3 to estimating the objective value of program (2) results in rX<l. Recalling p≤2n−1<n2+9n+2/2, it follows that l<n, which implies rX<n. Hence, we prove the desired conclusion of the lemma due to the equivalence of programs (2) and (6).
Lemma4 shows that optimal solutions of program (6) lie exactly on the boundary of the feasible region since the rank of that optimal solutions is smaller than n. This says that there exists a nonzero vector f=f1,f2,…,f2n−1T∈ℝ2n−1 such that program (6) and the following semidefinite program have the same solution:(16)minfTx,s.t.Ax=b,ℋTx≽0.
Hence, it suffices to estimate the objective value of program (16). It is easy to see that system (16) is a semidefinite program, which can be solved by many methods, for example, the interior point method [30] and the feasible direction method [31]. However, these methods just give numerical solutions for given A and b and cannot provide analytical solutions for any A and b. Hence, we explore a novelty method to solve this issue.
Recall that the dual of program (16) is given by(17)minbTλ,s.t.ℋX=f+ATλ,X≽0.where λ∈ℝp and X∈ℝn×n are associated multipliers.Hereafter, we state a lemma showing that the strict complementarity holds almost everywhere, whose most essential nature is given by ([32], Lemma 2).Lemma 5.
Suppose thatx∗ and λ∗,X∗ are primal and dual optimal solutions, respectively. Then, we have that(18)rX∗+rℋTx∗=nholds almost everywhere.Proof.
For program (16), the KKT conditions are(19)Ax∗=b,ℋX∗=f+ATλ∗,X∗ℋTx∗=0,X∗≽0,ℋTx∗≽0.
LetrX∗=r and rℋTx∗=s. Using the complementarity conditions X∗ℋTx∗=0, we have r+s≤n and eigendecompositions as follows:(20)X∗=Qdiagμ1,…,μr,0,0,…,0QT,ℋTx∗=Qdiag0,0,…,0,η1,…,ηsQT,with Q∈ℝn×n and QTQ=I. Plunging eigendecompositions (20) into the KKT system, (19) yields the following system of equations:(21)Ax∗=b,ℋQdiagμ1,…,μr,0,0,…,0QT=f+ATλ∗,ℋTx∗=Qdiag0,0,…,0,η1,…,ηsQT,QTQ=I.
This is a system ofp+2n−1+nn+1/2+nn+1/2 equations in 2n+p+r+s+n2 variables xi∗,μi,ϑi,ηi,τi,Qij. If r+s<n, the system is unsolvable almost. Hence, r+s=n holds almost everywhere. We derive the conclusion of the lemma.
Letβ=1,t,…,t2n−1T∈ℝ2n−1. According to Lemma 2, program (17) can be represented as the following semi-infinite program,(22)minbTλ,s.t.AβTλ≥−fTβ,∀β∈ℝ2n−1.
The lemma below states that the feasible set of program (22) is bounded.Next, we will establish the main result on a lower bound on the optimal value of the positive semidefinite Hankel matrix rank minimization problem.Theorem 1.
IfA is full rank and the Slater condition holds for program (16), then the objective value of the positive semidefinite Hankel matrix rank minimization problem (program (6)), denoted as v∗, is almost not smaller than p/2, that is, v∗≥p/2.Proof.
Based on Lemma4 and the Slater condition, the solution set of program (22) is nonempty and finite. Let λ∗ be an optimal solution of program (22). Then, λ∗ is a local minimizer of the following program:(23)minbTλ,s.t.AβiTλ=−fTβi,i∈Iλ∗,where Iλ∗ is an finite index set of the active constraints of problem (22) at λ∗ since if Iλ∗ is infinite, we can select its finite subset such that, for all i in the subset AβiT,λ=−fTβi holds. Thus, λ∗ satisfies the following KKT system:(24)b=∑i=1Iλ∗μiAβi,(25)AβiTλ=−fTβi,i∈Iλ∗,where μ is the corresponding Lagrange multiplier vector.
Equation (24) is a system of p equations in 2Iλ∗ variables μi,λi. If 2Iλ∗>p, the system is almost unsolvable. Hence, Iλ∗≤p/2 holds almost everywhere. Moreover, for i∈Iλ∗, we have AβiTλ∗=−fTβi, which means ℋX∗βi=β˜iX∗β˜i=0 since ℋX∗=f+ATλ∗, where β˜i=1,tj,…,tjnT. Thus, X∗β˜i=0 since X≽0. This says that rX∗≤n−Iλ∗. Consequently, according to the conclusion of Lemma 5, we almost have(26)rℋTx∗=n−rX∗≥n−n−Iλ∗≥p2.


## 4. Conclusion

This paper focuses on approximating the global optimal value of a Hankel matrix rank minimization problem subjective to linear constraints. A lower bound for this optimization problem is provided based on some conclusions from nonnegative polynomials, dual theorem, and semi-infinite problems. We conclude that the lower bound is almost half of the number of linear constraints of the problem. This result is useful for simplifying the requirement of guessing the rank of the objective matrix in existing methods for solving such problem.



---

*Source: 2524016-2021-02-11.xml*