text:
# Trace Zero Cryptography

In 1998 Gerhard Frey firstly proposed using trace zero varieties for cryptographic purpose. These varieties are subgroups of the divisor class group on a low genus hyperelliptic curve defined over a finite field. These groups can be used to establish asymmetric cryptography using the discrete logarithm problem as cryptographic primitive.

Trace zero varieties feature a better scalar multiplication performance than elliptic curves. This allows a fast arithmetic in this groups, which can speed up the calculations with a factor 3 compared with elliptic curves and hence speed up the cryptosystem.

Another advantage is that for a groups of cryptographically relevant size, the order of the group can simply be calculated using the characteristic polynomial of the Frobenius endomorphism. This is not the case, for example, in elliptic curve cryptography when the group of points of an elliptic curve over a prime field is used for cryptographic purpose.

However to represent an element of the trace zero variety more bits are needed compared with elements of elliptic or hyperelliptic curves. Another disadvantage, is the fact, that it is possible to reduce the security of the TZV of 1/6th of the bit length using cover attack.

## Mathematical background

A hyperelliptic curve C of genus g over a prime field ${\displaystyle \mathbb {F} _{q}}$ where q = pn (p prime) of odd characteristic is defined as

${\displaystyle C:~y^{2}+h(x)y=f(x),}$

where f monic, deg(f) = 2g + 1 and deg(h) ≤ g. The curve has at least one ${\displaystyle \mathbb {F} _{q}}$-rational Weierstraßpoint.

The Jacobian variety ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$ of C is for all finite extension ${\displaystyle \mathbb {F} _{q^{n}}}$ isomorphic to the ideal class group ${\displaystyle \operatorname {Cl} (C/\mathbb {F} _{q^{n}})}$. With the Mumford's representation it is possible to represent the elements of ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$ with a pair of polynomials [u, v], where u, v${\displaystyle \mathbb {F} _{q^{n}}[x]}$.

The Frobenius endomorphism σ is used on an element [u, v] of ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$ to raise the power of each coefficient of that element to q: σ([u, v]) = [uq(x), vq(x)]. The characteristic polynomial of this endomorphism has the following form:

${\displaystyle \chi (T)=T^{2g}+a_{1}T^{2g-1}+\cdots +a_{g}T^{g}+\cdots +a_{1}q^{g-1}T+q^{g},}$

where ai in ℤ

With the Hasse–Weil theorem it is possible to receive the group order of any extension field ${\displaystyle \mathbb {F} _{q^{n}}}$ by using the complex roots τi of χ(T):

${\displaystyle |J_{C}(\mathbb {F} _{q^{n}})|=\prod _{i=1}^{2g}(1-\tau _{i}^{n})}$

Let D be an element of the ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$ of C, then it is possible to define an endomorphism of ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$, the so-called trace of D:

${\displaystyle \operatorname {Tr} (D)=\sum _{i=0}^{n-1}\sigma ^{i}(D)=D+\sigma (D)+\cdots +\sigma ^{n-1}(D)}$

Based on this endomorphism one can reduce the Jacobian variety to a subgroup G with the property, that every element is of trace zero:

${\displaystyle G=\{D\in J_{C}(\mathbb {F} _{q^{n}})~|~{\text{Tr}}(D)={\textbf {0}}\},~~~({\textbf {0}}{\text{ neutral element in }}J_{C}(\mathbb {F} _{q^{n}})}$

G is the kernel of the trace endomorphism and thus G is a group, the so-called trace zero (sub)variety (TZV) of ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$.

The intersection of G and ${\displaystyle J_{C}(\mathbb {F} _{q})}$ is produced by the n-torsion elements of ${\displaystyle J_{C}(\mathbb {F} _{q})}$. If the greatest common divisor ${\displaystyle \gcd(n,|J_{C}(\mathbb {F} _{q})|)=1}$ the intersection is empty and one can compute the group order of G:

${\displaystyle |G|={\dfrac {|J_{C}(\mathbb {F} _{q^{n}})|}{|J_{C}(\mathbb {F} _{q})|}}={\dfrac {\prod _{i=1}^{2g}(1-\tau _{i}^{n})}{\prod _{i=1}^{2g}(1-\tau _{i})}}}$

The actual group used in cryptographic applications is a subgroup G0 of G of a large prime order l. This group may be G itself.[1][2]

There exist three different cases of cryptograpghical relevance for TZV:[3]

• g = 1, n = 3
• g = 1, n = 5
• g = 2, n = 3

## Arithmetic

The arithmetic used in the TZV group G0 based on the arithmetic for the whole group ${\displaystyle J_{C}(\mathbb {F} _{q^{n}})}$, But it is possible to use the Frobenius endomorphism σ to speed up the scalar multiplication. This can be archived if G0 is generated by D of order l then σ(D) = sD, for some integers s. For the given cases of TZV s can be computed as follows, where ai come from the characteristic polynomial of the Frobenius endomorphism :

• For g = 1, n = 3: ${\displaystyle s={\dfrac {q-1}{1-a_{1}}}{\bmod {\ell }}}$
• For g = 1, n = 5: ${\displaystyle s={\dfrac {q^{2}-q-a_{1}^{2}q+a_{1}q+1}{q-2a_{1}q+a_{1}^{3}-a_{1}^{2}+a_{1}-1}}{\bmod {\ell }}}$
• For g = 2, n = 3: ${\displaystyle s=-{\dfrac {q^{2}-a_{2}+a_{1}}{a_{1}q-a_{2}+1}}{\bmod {\ell }}}$

Knowing this, it is possible to replace any scalar multiplication mD (|m| ≤ l/2) with:

${\displaystyle m_{0}D+m_{1}\sigma (D)+\cdots +m_{n-1}\sigma ^{n-1}(D),~~~~{\text{where }}m_{i}=O(\ell ^{1/(n-1)})=O(q^{g})}$

With this trick the multiple scalar product can be reduced to about 1/(n − 1)th of doublings necessary for calculating mD, if the implied constants are small enough.[4][5]

## Security

The security of cryptographic systems based on trace zero subvarieties according to the results of the papers[6][7] comparable to the security of hyper-elliptic curves of low genus g' over ${\displaystyle \mathbb {F} _{p'}}$, where p' ~ (n − 1)(g/g' ) for |G| ~128 bits.

For the cases where n = 3, g = 2 and n = 5, g = 1 it is possible to reduce the security for at most 6 bits, where |G| ~ 2256, because one can not be sure that G is contained in a Jacobian of a curve of genus 6. The security of curves of genus 4 for similar fields are far less secure.

## Cover attack on a trace zero crypto-system

The attack published in[8] shows, that the DLP in trace zero groups of genus 2 over finite fields of characteristic diverse than 2 or 3 and a field extension of degree 3 can be transformed into a DLP in a class group of degree 0 with genus of at most 6 over the base field. In this new class group the DLP can be attacked with the index calculus methods. This leads to a reduction of the bit length 1/6th.

## Notes

1. ^ G. Frey and T. Lange: "Mathematical background of public key cryptography"
2. ^ T. Lange: "Trace zero subvariety for cryptosystems"
3. ^ R. M. Avanzi and E. Cesena: "Trace zero varieties over fields of characteristic 2 for cryptographic applications"
4. ^ R. M. Avanzi and E. Cesena: "Trace zero varieties over fields of characteristic 2 for cryptographic applications"
5. ^ T. Lange: "Trace zero subvariety for cryptosystems"
6. ^ T. Lange: "Trace zero subvariety for cryptosystems"
7. ^ R. M. Avanzi and E. Cesena: "Trace zero varieties over fields of characteristic 2 for cryptographic applications"
8. ^ C. Diem and J. Scholten: "An attack on a trace-zero cryptosystem"


text:
On testing for high-dimensional white noise

# On testing for high-dimensional white noise

\fnms  Zeng \snmLilabel=e1]zxl278@psu.edu [    \fnms  Clifford \snmLam label=e3]c.lam2@lse.ac.uk [    \fnms  Jianfeng \snmYao label=e2]jeffyao@hku.hk [    \fnms  Qiwei \snmYaolabel=e4]q.yao@lse.ac.uk [ London School of Economics, Pennsylvania State University, The University of Hong Kong Department of Statistics
Pennsylvania State University
Department of Statistics and Actuarial Science
The University of Hong Kong
Department of Statistics
London School of Economics and Political Science
###### Abstract

Testing for white noise is a classical yet important problem in statistics, especially for diagnostic checks in time series modeling and linear regression. For high-dimensional time series in the sense that the dimension is large in relation to the sample size , the popular omnibus tests including the multivariate Hosking and Li-McLeod tests are extremely conservative, leading to substantial power loss. To develop more relevant tests for high-dimensional cases, we propose a portmanteau-type test statistic which is the sum of squared singular values of the first lagged sample autocovariance matrices. It, therefore, encapsulates all the serial correlations (upto the time lag ) within and across all component series. Using the tools from random matrix theory and assuming both and diverge to infinity, we derive the asymptotic normality of the test statistic under both the null and a specific VMA(1) alternative hypothesis. As the actual implementation of the test requires the knowledge of three characteristic constants of the population cross-sectional covariance matrix and the value of the fourth moment of the standardized innovations, non trivial estimations are proposed for these parameters and their integration leads to a practically usable test. Extensive simulation confirms the excellent finite-sample performance of the new test with accurate size and satisfactory power for a large range of finite combinations, therefore ensuring wide applicability in practice. In particular, the new tests are consistently superior to the traditional Hosking and Li-McLeod tests.

[
\kwd
\startlocaldefs\endlocaldefs\setattribute

journalname

\runtitle

On testing a high-dimensional white noise

{aug}111Li’s research was supported by was supported by NIDA, NIH grants P50 DA039838, a NSF grant DMS 1512422 and National Nature Science Foundation of China (NNSFC), 11690015.

and and and

class=AMS] \kwd[Primary ]62M10, 62H15 \kwd[; secondary ]15A52

large autocovariance matrix \kwdHosking test \kwdLi-McLeod test \kwdhigh-dimensional time series \kwdrandom matrix theory

## 1 Introduction

Testing for white noise is an important problem in statistics. It is indispensable in diagnostic checking for linear regression and linear time series modeling in particular. The surge of recent interests in modeling high-dimensional time series adds a further challenge: diagnostic checking demands the testing for high-dimensional white noise in the sense that the dimension of time series is comparable to or even greater than the sample size (i.e., the observed length of the time series). One prominent example showing the need for diagnostic checking in high-dimensional time series concerns the vector autoregressive model, which has a large literature. When the dimension is large, most existing works regularize the fitted models by Lasso (Hsu et al., 2008; Haufe et al., 2009; Shojaie and Michailidis, 2010; Basu and Michailidis, 2015), Dantzig penalization (Han and Liu, 2015), banded autocovariances (Bickel and Gel, 2011), or banded auto-coefficient matrices (Guo et al., 2016). However, none of them have developed any residual-based diagnostic tools. Another popular approach is to represent high-dimensional time series by lower-dimensional factors. See for example, Stock and Watson (1989, 1998, 1999), Forni et al. (2000, 2005), Bai and Ng (2002), Lam and Yao (2012) and Chang et al. (2015). Again, there is a pertinent need to develop appropriate tools for checking the validity of the fitted factor models through careful examination of the residuals.

There are several well-established white noise tests for univariate time series (Li, 2004). Some of them have been extended for testing vector time series (Hosking, 1980; Li et al., 1981; Lütkepohl, 2005). However, these methods are designed for the cases where the dimension of the time series is small or relatively small compared to the sample size. For the purpose of model diagnostic checking, the so-called omnibus tests are often adopted which are designed to detect any forms of departure from white noise. The celebrated Box-Pierce portmanteau test and its variations are the most popular omnibus tests. The fact that the Box-Pierce test and its variations are asymptotically distribution-free and -distributed under the null hypothesis makes them particularly easy to use in practice. However, it is well known in the literature that the slow convergence to their asymptotic null distributions is particularly pronounced in multivariate cases. On the other hand, testing for high-dimensional time series is still in an infancy stage. To our best knowledge, the only available methods are Chang, Yao and Zhou (2017) and Tsay (2017).

To appreciate the challenge in testing for a high-dimensional white noise, we refer to an example reported in Section 3.1 below where say, we have to check the residuals from a fitted multivariate volatility for a portfolio containing stocks using their daily returns over a period of one semester. The length of the returns time series is then approximately . Table 1 shows that the two variants of the multivariate portmanteau test, namely the Hosking and Li-McLeod tests, all have actual sizes around 0.1%, instead of the nominal level of 5%. These omnibus tests are thus extremely conservative and they will not be able to detect an eventual misfitting of the volatility model.

The above example illustrates the following fact, which is now better understood: many popular tools in multivariate statistics are severely challenged by the emergence of high-dimensional data, and they need to be re-examined or corrected. Recent advances in high-dimensional statistics demonstrate that feasible and quality solutions to these high-dimensional challenges can be obtained by exploiting tools of random matrix theory via a precise spectral analysis of large sample covariance or sample autocovariance matrices. For a review on such progress, we refer to Johnstone (2007), Paul and Aue (2014) and monograph Yao et al. (2015). In particular, asymptotic results found in this context using random matrix theory exhibit fast convergence rates, and hence provide satisfactory finite sample approximation for data analysis.

This paper proposes a new method for testing high-dimensional white noise. The test statistic encapsulates the serial correlations within and across all component series. Precisely, the statistic is the sum of the squared singular values of several lagged sample autocovariance matrices. Using random matrix theory, asymptotic normality for the test statistics under the null is established under the Marčenko-Pastur asymptotic regime where and are large and comparable. Next, original methods are proposed for estimation of a few parameters in the limiting distribution in order to get a fully implementable version of the test. The asymptotic power of the test under a specific alternative of first-order vector moving average process (VMA(1)) has also been derived. Extensive simulation demonstrates excellent behavior of the proposed tests for a wide array of combinations of , with accurate size and satisfactory power. In this paper, we also explore the reasons why the popular multivariate Hosking and Li-McLeod tests are no longer reliable when the dimension is large in relation to the sample size.

The rest of the paper is organized as follows. Section 2 presents the main contributions of the paper. A new high-dimensional test for white noise is introduced, its asymptotic distributions under both the null and the VMA(1) alternative hypothesis are established. Section 3 reports extensive Monte-Carlo experiments which assess the finite sample behavior of the tests. Whenever possible, comparison is made with the popular Hosking and Li-McLeod tests. Numerical evidence also indicates that the new test is more powerful than that of Chang, Yao and Zhou (2017). Section 4 collects all the technical proofs.

## 2 A test for high-dimensional white noise

Let be observations from a complex-valued linear process of the form

 xt=∑l≥0Alzt−l,

where are coefficient matrices, is a sequence of -dimensional random vectors such that, if the coordinates of are , then the two dimensional array of variables are i.i.d. satisfying the moment conditions and . Hence , and depends on only. Note that is the population covariance matrix of the time series. The goal is to test the null hypothesis

 H0: xt=A0zt (2.1)

where is unknown. This in fact tests the independence instead of linear independence (i.e. for all ), which is however a common practice in the literature of white noise tests. Throughout the paper, the complex adjoint of a matrix (or vector) is denoted by . For , let be the lag sample autocovariance matrix

 ˆΣτ=1TT∑t=1xtx∗t−τ.

where by convention when . Under the null hypothesis, for , and a natural test statistic is the sum of squared singular values of the first lagged sample autocovariance matrices:

 Gq=q∑τ=1Tr(ˆΣ∗τˆΣτ)=q∑τ=1∑jα2τ,j,

where are the singular values of , and denotes the trace operation for square matrices. We reject the null hypothesis for large values of .

Notice that the setting here allows for complex-valued observations: this is important for applications in areas such as signal processing where signal time series are usually complex-valued. However, for the sake of presentation, we mostly focus on the real-valued case in the subsequent sections. Directions on how the tests can be extended to accommodate complex-valued observations will be given in the last Section 2.4.

### 2.1 High dimensional asymptotics

We adopt the so-called Marčenko-Pastur regime for asymptotic analysis, i.e. we assume when . This asymptotic framework has been widely employed in the literature on high-dimensional statistics, see, Johnstone (2007), Paul and Aue (2014), also monograph Yao et al. (2015) and the references within. Most of the results in this area concern sample covariance matrices only. However our test statistic is based on the sample autocovariance matrices, which is much less studied; see Liu et al. (2015) and Bhattacharjee and Bose (2016).

As a main contribution of the paper, we characterize the asymptotic distribution of in this high-dimensional setting when the observations are real-valued. We introduce the following limits whenever they exist: for ,

 sℓ=limp→∞1pTr(Σℓ0),sd,ℓ=limp→∞1pTr(Dℓ(Σ0)), (2.2)

where denotes the diagonal matrix consisting of the main diagonal elements of (here the in the index is a reminder of this diagonal structure).

###### Theorem 2.1.

Let be a fixed integer, and the following assertions hold.

1. is a sequence of real-valued independent random vectors with independent components satisfying and ;

2. is a sequence of semi-positive definite matrices with bounded spectral norm such that the limits and exist;

3. (Marčenko-Pastur regime). The dimension and the sample size grow to infinity in a related way such that .

Then when , the limiting distribution of the test statistic is

 Gq−qTc2ps21  d→  N(0,σ2(c)), (2.3)

where

 σ2(c)=2qc2s22+4q2c3(ν4−3)s21sd,2+8q2c3s21s2. (2.4)

The proof of this theorem is given in Section 4.

Let be the upper- quantile of the standard normal distribution at level . Based on Theorem 2.1, we obtain a procedure for testing the null hypothesis in (2.1) as follows.

 \em Reject ~{} H0 ~{}~{}if ~{}~{}{Gq−qTc2ps21>Zασ(c)}. (2.5)

The illustration in Section 3 indicates that the test above is much more powerful than some classical alternatives, especially when the dimension is growing linearly with the sample size . The power of this test is gained from gathering together the serial correlations from the first lags within and across all component series; see the definition of . Also note that the asymptotic mean of is , which grows linearly with (and ), while its asymptotic variance is a constant. This implies that even for moderately large , departure from white noise in the first lags of the autocovariance matrices is likely to result in a large and different mean, which will be a large multiple standard deviation away from since the standard deviation is constant.

However the test in (2.5) is not yet practically usable as it depends on (i) three characteristic constants, , and of the (population) cross-sectional covariance matrix and (ii) the fourth moment of the innovations . These issues are addressed below.

### 2.2 Estimation of the covariance characteristics s1 and s2

If the cross-sectional covariance matrix is known, consistent estimates of these characteristics are readily calculated from . By Slutsky’s Theorem, these estimates can substitute for the true ones in the asymptotic variance and the centering term . The test (2.5) still applies.

However, the population covariance matrix is in general unknown and the situation becomes challenging as estimating a general is somehow out of reach without specific assumptions on its structure. Luckily, as observed previously, we only need consistent estimates of the three characteristics. First of all, in the setting of Theorem 2.1 and under the null, it is not difficult to find consistent estimators for these characteristics, thus a consistent estimator of the limiting variance . The situation is much more intricate for the centering term . Suppose is a consistent estimator of . Plugging it into the centering term leads to

 Gq,1:=Gq−qTc2p^s21={Gq−qTc2ps21}+qTc2p{s21−^s21} . (2.6)

Because of the multiplication by here, the asymptotic distribution would remain the same only if the estimation error is of order . This is however not the case and in general the error is exactly of the order and converges to some other normal distribution.

Our method is as follows. First we establish the joint asymptotic distribution of and for a natural estimator . This result extends Theorem 2.1 which addresses the statistic only. Next, the asymptotic null distribution of the “feasible” test statistic is readily obtained as a simple consequence.

Precisely, consider the sample covariance matrix and define the natural estimators of and as

 ^s1=1pTr(ˆΣ0),^s2=1pTr(ˆΣ20).
###### Theorem 2.2.

Assume the same conditions as in Theorem 2.1, then when , we have

 ⎛⎝p(^s21−s21)Gq−qTc2ps21⎞⎠d→
 N2((00), (4c(ν4−3)s21sd,2+8cs21s24qc2(ν4−3)s21sd,2+8qc2s21s24qc2(ν4−3)s21sd,2+8qc2s21s2σ2(c))),

where the variance is given in (2.4).

The proof of this theorem is relegated to Section 4.

Applying Theorem 2.2 to the decomposition (2.6), the following proposition establishes the asymptotic null distribution of the feasible statistic . Second order terms of the mean and variance of are also provided to improve finite sample performance.

###### Proposition 2.1.

Assume the same conditions as in Theorem 2.2 and the observations are real-valued, we have

 Gq,1=Gq−qTc2p^s21d→N(0,ξ2(c)), (2.7)

where . Meanwhile,

 E(Gq,1)=−qT2(2Tr(Σ20)+(ν4−3)Tr(D2(Σ0))), E(^s1)=1pTr(Σ0), Var(Gq,1)=2qT2Tr2(Σ20)+qT3(2Tr(Σ20)+(ν4−3)Tr(D2(Σ0)))2+o(1T), E(^s2)=1pTr(Σ20)+1pTTr2(Σ0)+1pT(Tr(Σ20)+(ν4−3)Tr(D2(Σ0))).

Now we aim at consistent estimates for the unknown quantity in the asymptotic variance . It is well known that almost surely (Bai et al. (2010)),

 ^s1→s1, ^s2→s2+cs21.

Therefore is a strongly consistent estimator of .

In summary, when is unknown, we obtain a procedure for testing the null hypothesis of white noise (2.1) as follows:

 \em Reject H0 if ~{}~{}{Gq−qTc2p^s21>Zα~ξ} (2.8)

where

### 2.3 Finite sample correction and estimation for non-Gaussian innovations

Although the test procedure (2.8) is already practically usable, it can be further improved by finite sample corrections provided in Proposition 2.1 which are especially useful for non-Gaussian population where . To this goal, it remains to obtain a consistent estimate for (i) the covariance characteristic

 sd,2=1pp∑i=1d2i=1pTr(D2(Σ0)),

where is the th diagonal element of , and (ii) the fourth moment of the innovations.

(i) Estimation of .  By its very definition, can be consistently estimated by its sample counterpart

 ~di=1TT∑t=1x2it.

It follows that a consistent estimator for is simply .

(ii) Estimation of .  This is again a non trivial problem which has not been touched yet in the literature (to our best knowledge). In order to get rid of the role of the unknown cross-sectional covariance matrix , we adopt the following splitting strategy: the original data are split into two halves of length and , respectively (). Define the two corresponding sample cross-sectional covariance matrices

 Sn,1=1T1T1∑t=1xtx∗t,Sn,2=1T2T2∑t=1xt+T1x∗t+T1. (2.9)

This yields the corresponding -ratio, or Fisher matrix, . Observe that this matrix does not depend on the value of the cross-sectional covariance so that in what follows we can assume .

Let be the eigenvalues of . Define test functions where are some positive constants. For each , we have an eigenvalue statistic of the Fisher matrix

 XT,k=fk(λ1)+⋯+fk(λp)−p∫fk(x)dFcp,1,cp,2(x) ,

where () and is the limiting Wachter distribution with index , see formula (3.1) in Zheng (2012). It is proved on page 452 of the reference, when grow proportionally to infinity,

 XT,k=uT,k+vT,kν4+εT,k , (2.10)

where are constants depending on and , and is a centered and asymptotically Gaussian error. Then the least squares estimator of using the above regression model leads to a consistent estimate, say for the unknown parameter.

Under the null hypothesis, the observations are independent. We may repeat this estimation procedure, say times, by taking random splits of the initial sample. The final estimate of is then taken to be the average of the estimates .

Finally we can implement the following test procedure with finite sample correction for the null hypothesis of white noise (2.1):

 \em Reject H0 if ~{}~{}{G∗q,1=Gq−qTc2p^s21+1T⋅qcp(2~s2+(^ν4−3)~sd,2)>Zα^ξ} (2.11)

where

 ^ξ2=2qc2p~s22+1T⋅qc2p(2~s2+(^ν4−3)~sd,2)2

with the above estimator for the fourth moment.

### 2.4 Tests when the observations are complex-valued

To proceed, we first define where is a proper complex random vector, and is such that is Hermitian with (Properness of a complex random vector means that ). We immediately have

 0=E(ztzTt)=E(z2it)Ip,

so that for all and . It also implies that . Since , we have

 E(xtxTt)=E(Σ1/20ztzTtΣT/20)=0,

so that we are also assuming an observed vector is proper.

From Corollary 4.1, since from the properness of , the asymptotic covariance of is then

 Var(Gq)→qc2s22+4q2c3s21[(ν4−2)sd,2−s′2+2sr,2],

where , , with , the matrix of the real parts of all entries in .

Using Lemma A.1, defining to be the matrix of the imaginary parts of all entries in , we have

 2Tr(R2(Σ0))−Tr(Σ0ΣT0) =2Tr(Σ0R(Σ0))−Tr(Σ0(R(Σ0)−iI(Σ0))) =Tr(Σ0(R(Σ0)+iI(Σ0)))=Tr(Σ20),

so that . The asymptotic variance for is then

 Var(Gq)→σ2(c)=qc2s22+4q2c3s21[(ν4−2)sd,2+s2],

which can be estimated consistently using the estimators suggested in Section 2.2.

### 2.5 Testing power of Gq,1

In this section, we look into the power function of the tests when an alternative hypothesis is specified. Here we assume that under , the observations follows from a real-valued -dimensional first-order vector moving average process, VMA(1) in short, of the form

 H1: xt=A0zt+A1zt−1, (2.12)

where , are coefficient matrices. Now we only consider the asymptotic behavior of our test statistic and when since higher order autocorrelations of are null under both and .

Denote

 ˜Σ0=A∗0A0,˜Σ1=A∗1A1,˜Σ01=A∗0A1,

we characterize the joint limiting distribution of and under the VMA(1) alternative (2.12) as follows.

###### Theorem 2.3.

Assume that

1. is a sequence of real-valued independent random vectors with independent components satisfying and ;

2. , and all have bounded spectral norm and for integers , , the limits exist;

3. (Marčenko-Pastur regime). The dimension and the sample size grow to infinity in a related way such that .

Then under the VMA(1) alternative (2.12), the joint limiting distribution of the and is

 (σ2GσGSσGSσ2S)−1/2(G1−μGTc2p^s21−μS)d→N2(0, I2),

where

 μG =1TTr2(˜Σ0+˜Σ1)+Tr(˜Σ0˜Σ1)+2TTr2(˜Σ01) +1T[Tr(˜Σ0˜Σ1)+(ν4−3)Tr(D(˜Σ0)D(˜Σ1))], μS =1TTr2(˜Σ0+˜Σ1)+4T2Tr(˜Σ01˜Σ∗01) +1T2[2Tr(˜Σ0+˜Σ1)2+(ν4−3)Tr(D2(˜Σ0+˜Σ1))],
 σ2S= 4T3Tr2(˜Σ0+˜Σ1)[2Tr(˜Σ0+˜Σ1)2+(ν4−3)Tr(D2(˜Σ0+˜Σ1))] +16T3Tr2(˜Σ0+˜Σ1)Tr(˜Σ01˜Σ∗01)+Rn,

and

 σ2G= 4T3Tr2(˜Σ0+˜Σ1)[2Tr(˜Σ0+˜Σ1)2+(ν4−3)Tr(D2(˜Σ0+˜Σ1))] +8T2Tr(˜Σ0+˜Σ1)[2Tr(˜Σ0˜Σ1(˜Σ0+˜Σ1))+(ν4−3)Tr(D(˜Σ0˜Σ1)D(˜Σ0+˜Σ1))] +8T2Tr(˜Σ01˜Σ∗01)Tr(˜Σ20+˜Σ21)+16T2Tr(˜Σ01˜Σ1)Tr(˜Σ01˜Σ0) +16T2Tr(˜Σ01)[Tr(˜Σ20˜Σ∗01)+Tr(˜Σ21˜Σ01)+2Tr(˜Σ1˜Σ01˜Σ0)] +4TTr(˜Σ∗01˜Σ01˜Σ20+˜Σ01˜Σ∗01˜Σ21+2˜Σ∗01˜Σ1˜Σ01˜Σ0) +16T3Tr2(˜Σ0+˜Σ1)Tr(˜Σ01˜Σ∗01)+16T3Tr2(˜Σ01)Tr(˜Σ0+˜Σ1)2 +32T3Tr(˜Σ0+˜Σ1)Tr(˜Σ01)Tr(˜Σ01(˜Σ0+˜Σ1)) +4TTr(˜Σ01˜Σ∗01˜Σ∗01˜Σ01)+12T2Tr2(˜Σ01˜Σ∗01)+16T2Tr(˜Σ01)Tr(˜Σ01˜Σ∗01˜Σ∗01) +16T3Tr2(˜Σ01)[Tr(˜Σ01)2+2Tr(˜Σ01˜Σ∗01)+(ν4−3)Tr(D2(˜Σ01))]+8T2Tr2(˜Σ1˜Σ01) +16T3Tr(˜Σ01)Tr(˜Σ0+˜Σ1)[2Tr(˜Σ01(˜Σ0+˜Σ1))+(ν4−3)Tr(D(˜Σ01)D(˜Σ0+˜Σ1))] +8T2Tr2(˜Σ0˜Σ01)+16T2Tr(˜Σ01)[2Tr(˜Σ0˜Σ1˜Σ01)+(ν4−3)Tr(D(˜Σ0˜Σ1)D(˜Σ01))]+Rn,
 σGS= 4T3Tr2(˜Σ0+˜Σ1)[2Tr(˜Σ0+˜Σ1)2+(ν4−3)Tr(D2(˜Σ0+˜Σ1))] +4T2Tr(˜Σ0+˜Σ1)[2Tr(˜Σ0˜Σ1(˜Σ0+˜Σ1))+(ν4−3)Tr(D(˜Σ0˜Σ1)D(˜Σ0+˜Σ1))] +8T3Tr(˜Σ01)Tr(˜Σ0+˜Σ1)[2Tr(˜Σ01(˜Σ0+˜Σ1))+(ν4−3)Tr(D(˜Σ01)D(˜Σ0+˜Σ1))] +16T3Tr(˜Σ0+˜Σ1)Tr(˜Σ01)Tr(˜Σ01(˜Σ0+˜Σ1))+Rn.

Here the ’s, possibly different, represent remainders which have smaller orders than the other terms listed in , and , respectively.

The proof of this theorem is relegated to Section 4. Similarly, applying Theorem 2.3 to the decomposition (2.6), the following proposition establishes the asymptotic distribution of our test statistic under the VMA(1) alternative (2.12) when .

###### Proposition 2.2.

Assume the same conditions as in Theorem 2.3, when and the observables are real-valued, we have

 (2.13)

where

 μG1,1= Tr(˜Σ0˜Σ1)+2TTr2(˜Σ01)+1T[Tr(˜Σ0˜Σ1)+(ν4−3)Tr(D(˜Σ0)D(˜Σ1))] −4T2Tr(˜Σ01˜Σ∗01)−1T2[2Tr(˜Σ0+˜Σ1)2+(ν4−3)Tr(D2(˜Σ0+˜Σ1))],
 σ2G1,1 =2T2Tr2(˜Σ20+˜Σ21)+4T[2Tr(˜Σ0˜Σ1)2+(ν4−3)Tr(D2(˜Σ0˜Σ1))] +6T2Tr2(˜Σ0˜Σ1)+8T2Tr(˜Σ01˜Σ∗01)Tr(˜Σ20+˜Σ21)+16T2Tr(˜Σ01˜Σ1)Tr(˜Σ01˜Σ0)

format: plain


text:
# Use the cross product to find the sin of an angle then prove it

1. Sep 17, 2011

### shemer77

1. The problem statement, all variables and given/known data
Leta theta be the angle between the vectors u=2i +3j -6k and v=2i + 3j+6k
A) use the dot product to find cos theta
b) use the cross product to find sin theta
c) confirm that sin^2(theta) + cos^2(theta)=1

3. The attempt at a solution
I got a to be 117 degrees, but however b and c are stumping me, whenever I try to do b I get an the cross product and then try to solve for theta but i get an error using my calculator, I rechecked my calculations twice and everything make sense am I doing something wrong or is it really not possible.

2. Sep 17, 2011

### dynamicsolo

It would be more helpful to someone assisting you if you explained what you did for part (b), in order to understand why you are getting an error...

(And I get an angle of 118º for theta.)

3. Sep 17, 2011

### shemer77

well all i did was the cross product of u and v which came out to 36i -24j+0k and i took the norm of that which came out to 12*sqrt(13) and I divided that by the norm of u * the norm of v which is 49. so I had 12*sqrt(13)/49 and i took the inverse sin of that. which would obviously give me an error. But I dont see what I did wrong all my calculations are correct.

4. Sep 17, 2011

### dynamicsolo

Check how you have input $\frac{12\sqrt{13}}{49}$ ; this is a positive number smaller than 1 . Is your "error" that you don't get the same angle as you did for the arccosine? Don't forget that the range of arccosine is 0º to 180º , but the range of arcsine is -90º to 90º ; the arcsine result for theta (out of a calculator) is the supplement of the correct value. (The angle theta is in the second quadrant.)

Part (c) sidesteps this anyway, since you are simply asked to sum the squares of your values from parts (a) and (b)... [EDIT: You must have gotten cos(theta) = -23/49 to get the angle of 118º . The sum of the squares does give you 1 .]

Last edited: Sep 17, 2011
5. Sep 17, 2011

### shemer77

ah awesome man, I got it thanks for your help!!!


text:
# Definition:Sequence/Infinite Sequence

## Definition

An infinite sequence is a sequence whose domain is infinite.

That is, an infinite sequence is a sequence that has infinitely many terms.

Hence for an infinite sequence $\sequence {s_n}_{n \mathop \in \N}$ whose range is $S$, $\sequence {s_n}_{n \mathop \in \N}$ is an element of the set of mappings $S^{\N}$ from $\N$ to $S$.

On $\mathsf{Pr} \infty \mathsf{fWiki}$ all sequences are infinite sequence unless explicitly specified otherwise.

## Also known as

Treatments of this subject which approach the definition of a sequence from the direction of ordered tuples offer the term $\omega$-tuple for the concept of a tuple whose domain is (countably) infinite.

Some sources use the term denumerable sequence.


text:
# The generalized vertex cover problem and some variations

In this paper we study the generalized vertex cover problem (GVC), which is a generalization of various well studied combinatorial optimization problems. GVC is shown to be equivalent to the unconstrained binary quadratic programming problem and also equivalent to some other variations of the general GVC. Some solvable cases are identified and approximation algorithms are suggested for special cases. We also study GVC on bipartite graphs and identify some polynomially solvable cases. We show that GVC on bipartite graphs is equivalent to the bipartite unconstrained 0-1 quadratic programming problem. Integer programming formulations of GVC and related problems are presented and establish half-integrality property on some variables for the corresponding linear programming relaxations. We also discuss special cases of GVC where all feasible solutions are independent sets or vertex covers. These problems are observed to be equivalent to the maximum weight independent set problem or minimum weight vertex cover problem along with some algorithmic results.

There are no comments yet.

## Authors

• 2 publications
• 4 publications
• ### A polynomial time approximation schema for maximum k-vertex cover in bipartite graphs

The paper presents a polynomial time approximation schema for the edge-w...
09/18/2019 ∙ by Vangelis Th. Paschos, et al. ∙ 0

• ### Weighted Upper Edge Cover: Complexity and Approximability

Optimization problems consist of either maximizing or minimizing an obje...
11/06/2018 ∙ by Kaveh Khoshkhah, et al. ∙ 0

• ### Mapping Matchings to Minimum Vertex Covers: Kőnig's Theorem Revisited

It is a celebrated result in early combinatorics that, in bipartite grap...
04/18/2020 ∙ by Jacob Turner, et al. ∙ 0

• ### Integer Linear Programming Formulations for Double Roman Domination Problem

For a graph G= (V,E), a double Roman dominating function (DRDF) is a fun...
02/21/2019 ∙ by Qingqiong Cai, et al. ∙ 0

• ### Extension of vertex cover and independent set in some classes of graphs and generalizations

We consider extension variants of the classical graph problems Vertex Co...
10/10/2018 ∙ by Katrin Casel, et al. ∙ 0

• ### Practical Graph Bipartization with Applications in Near-Term Quantum Computing

We experimentally evaluate the practical state-of-the-art in graph bipar...
05/02/2018 ∙ by Timothy D. Goodrich, et al. ∙ 0

• ### LP-based algorithms for multistage minimization problems

We consider a multistage framework introduced recently where, given a ti...
09/23/2019 ∙ by Evripidis Bampis, et al. ∙ 0

##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

Let be a graph with . For each edge three real valued weights are associated. Also, for each vertex a weight is prescribed. For any subset , let , , , and

 f(U)=∑i∈Uci+∑(i,j)∈E0(U)q0ij+∑(i,j)∈E1(U)q1ij+∑(i,j)∈E2(U)q2ij.

Then the generalized vertex cover problem (GVC) is to find a set such that is minimized. Note that can be viewed as the ‘cost of’ not covering edge , can be viewed as the ‘cost of’ covering edge by selecting exactly one of its end points, and can be viewed as the ‘cost of’ over-covering edge . If the solution is an empty set , then the objective function is defined as .

GVC was introduced by Hassin and Levin [13] and it is a meaningful generalization of the well known minimum weight vertex cover problem (MWVCP) [14, 33] and the maximum weight independent set problem (MWISP) [4, 33]. Note that if for all , a large number and for all then, GVC reduces to MWVCP. Likewise, when , , for all , then GVC is equivalent to MWISP. (It may be noted that MWISP is normally presented as a maximization problem which is equivalent to minimization form indicated above). Hassin and Levin [13] although introduced GVC, they focused primarily on a special case of it where is assumed to be non-negative for all and for all . We denote this special case of GVC by GVC-HL and it may be noted that MWISP is not a special case of GVC-HL. In [13] two 2-approximation algorithms for GVC-HL are proposed , one based on linear programming, and the other based on the local-ratio technique [6]. When for all and , GVC is called uniform cost generalized vertex cover problem (UGVC). In [13] the complexity of UGVC has been studied for all possible values of and . They showed that GVC is polynomial time solvable in the following cases: 1) , 2) , 3) and there exists an integer such that . For the general case, UGVC is NP-hard [13]. Milanovic [23]

proposed a genetic algorithm to solve GVC-HL and reported experimental results comparing their algorithm with CPLEX and the 2-approximation algorithm given in

[13]. Kochenberger et. al. [20] compared an integer linear programming formulation and an integer quadratic programming formulations using the CPLEX solver.

Another special case of GVC where for all was considered by Houchbaum [16] and Bar-Yehuda et al. [7]. This problem is also known as the generalized vertex cover problem in the literature and for definiteness we denote this problem by GVC1. In fact, Houchbaum [16] and Bar-Yehuda et al.  [7] studied primarily a special case of GVC1 where for all , for all . We refer to this version of GVC1 as GVC1-HB. Houchbaum [16] provided an integer linear programming formulation of GVC1-HB and showed that the corresponding linear programming relaxation admits half integrality property. Bar-Yehuda et al. [7] provided an extension of a well known theorem by Nemhauser and Trotter [24] for the vertex cover problem (independent set problem) to GVC1-HB, and presented a -approximation algorithm on graphs with maximum degree of a node is bounded above by . They also presented a polynomial time approximation scheme (PTAS) for GVC1-HB on planner graphs, and a - approximation algorithm for a general graph. In the same paper they showed that GVC1-HB is NP-hard on complete graphs but solvable in polynomial time on bipartite graphs. Note that MWVCP is trivial on complete graphs.

The generalized independent set problem introduced by Hochbaum [16] is yet another special case of GVC. Here are assumed to be zero for all , and we denote this problem by GVC2. Hochbaum and Pathria [15] studied a special case of GVC2 where for all , for all . This version of GVC2 is denoted by GVC2-HP and the model have applications in Forest Harvesting. GVC2-HP in [15] was presented as a maximization problem with and . Clearly, this is equivalent to our definition of GVC2-HP. Kochenberger et al. [21] gave a nonlinear formulation for GVC2-HP and compare the computational effectiveness of this non-linear integer programming formulation with an available linear integer programming formulation.

Another problem closely related to GVC is the unconstrained binary quadratic programming problem (UBQP) studied by various authors [2, 11, 18, 19, 25]. Let be an symmetric matrix and be an

-vector. Then UBQP is to find an

such that

 n∑i=1aixi+n∑i=1n∑j=1qijxixj

is minimized (or maximized). Without loss of generality is chosen as zero for and we assume UBQP is presented as a minimization problem. Also the assumption that is symmetric is not a restriction, since can be replaced by to obtain an equivalent problem.

Given the matrix , let . The subgraph of the complete graph with the vertex set is called the support graph of . Then UBQP can be reformulated in terms of i.e; UBQP is equivalent to finding such that

 ∑i∈Uai+∑(i,j)∈E2(\mathbmitQ,U)2qij

is minimized (or maximized), where .

The bipartite unconstrained 0-1 quadratic program problem (BQP01) [10, 30, 31] is closely related to GVC on bipartite graphs. Let be an matrix, , . Then BQP01 is defined as

 Minimize   f(\mathbmitx,\mathbmity)=\mathbmitxT\mathbmitQ\mathbmity+\mathbmita\mathbmitx+\mathbmitb\mathbmity=m∑i=1aixi+n∑j=1bjyj+m∑i=1n∑j=1qijxiyj subject to:   \mathbmitx∈{0,1}m,\mathbmity∈{0,1}n.

Consider an instance of BQP01 with cost matrix of dimension . The support bipartite graph of the matrix is the bipartite graph , where , and . The BQP01 can be formulated as a graph theoretic optimization problem on as

 Minimized ϕ(U1,U2)=∑i∈U1∑j∈U2qij+∑i∈U1ai+∑j∈U2bj subject to: U1⊆V1,U2⊆V2.

It may be noted that the definition of support bipartite graph is different from that of a support graph. The support graph when the underlying graph is bipartite is different from a support bipartite graph.

In this paper we study the general problems GVC, GVC1, and GVC2. We show that all these problems are equivalent to each other and also equivalent to UBQP. When the underlying graph is bipartite, these are equivalent to BQP01 as well. However, it may be noted that although these equivalences are verified in terms of optimality, domination ratio [12], differential approximation ratio [9], the characteristics of these problems in terms of approximation ratio [33] and various special cases are different and hence it is interesting to explore various special cases of these problems as well. We present several complexity results related to GVC, GVC1, and GVC2 along with some polynomial solvable special cases. Integer programming formulations of GVC, GVC1, and GVC2 are presented and establish half-integrality property on some variables for the corresponding linear programming relaxations. We also present an approximation algorithm for GVC with the approximation ratio when , , and generalizing a result given in [13]. The approximation ratio for the algorithm becomes when for given , and for each edge , all three weights are in . When , the optimal solutions of GVC are vertex covers and this special case leads to the vertex cover problem with node and edge weights (VCPNEW). The problem VCPNEW and two of its special cases are shown to be equivalent to the minimum weight vertex cover problem (MWVCP) and shown that VCPNEW can be solved by an algorithm whenever MWVCP can be solved by an -algorithm for an appropriate if and for all . When , optimal solutions of GVC are independent sets and this special case leads to the independent set problem with node and edge weights (ISPNEW). The problem ISPNEW and two of its special cases are shown to be equivalent to the maximum weight independent set problem (MWISP).

The paper is organized as follows: In Section 2, we study the complexity of GVC. Different NP-hard special cases as well as polynomially solvable special cases are identified. Further we show that GVC, GVC1, GVC2, and UBQP are pairwise equivalent in the sense that an algorithm to compute an optimal solution to one problem can be used to compute an optimal solution to the other. We also show that GVC, GVC1, and GVC2 on bipartite graphs are equivalent to BQP01. Section 3 contains integer programming formulation of GVC and related problems, establish half-integrality property on some variables, and also discuss the approximation algorithm for GVC. Section 4 discusses VCPNEW, ISPNEW and some of their special cases. We also establish that VCPNEW is equivalent to MWVCP, and ISPNEW is equivalent to MWISP.

## 2 Complexity and Solvable cases

We first show that the problems GVC, GVC1, GVC2, and UBQP are equivalent from an optimality point of view, i.e., any one of these problems can be formulated as another in the sense that from an optimal solution to one, an optimal solution to another can be recovered.

###### Theorem 2.1.

GVC, GVC1, and GVC2 are equivalent.

###### Proof.

We first show that GVC can be formulated as GVC1. Given an instance of GVC, define

 c′i= ci+∑(i,j)∈E(q2ij−q1ij), ∀ i∈V and (1) q0′ij= q2ij−2q1ij+q0ij, (i,j)∈E. (2)

Now, consider the instance of GVC1 where is replaced by and is replaced by . Then, for any , the objective function of this GVC1 can be written as

 g(U)=∑i∈Uc′i+∑(i,j)∈E0(U)q0′ij=∑i∈U⎛⎝ci+∑(i,j)∈E(q2ij−q1ij)⎞⎠+∑(i,j)∈E0(U)(q2ij−2q1ij+q0ij).

The objective function of GVC is given by

 f(U)= ∑i∈Uci+∑(i,j)∈E0(U)q0ij+∑(i,j)∈E1(U)q1ij+∑(i,j)∈E2(U)q2ij. (3)

It can be verified that

 ∑(i,j)∈E2(U)q2ij = ∑(i,j)∈E,i∈Uq2ij+∑(i,j)∈E,j∈Uq2ij+∑(i,j)∈E0(U)q2ij−∑(i,j)∈Eq2ij and (4) ∑(i,j)∈E1(U)q1ij = ∑(i,j)∈E2q1ij−∑(i,j)∈E0(U)2q1ij−∑(i,j)∈E,i∈Uq1ij−∑(i,j)∈E,j∈Uq1ij. (5)

From (3), (4) and (5), we have

 f(U)= ∑i∈Uci+∑(i,j)∈E0(U)q0ij+∑(i,j)∈E2q1ij−∑(i,j)∈E0(U)2q1ij−∑(i,j)∈E,i∈Uq1ij−∑(i,j)∈E,j∈Uq1ij +∑(i,j)∈E,i∈Uq2ij+∑(i,j)∈E,j∈Uq2ij+∑(i,j)∈E0(U)q2ij−∑(i,j)∈Eq2ij, = ∑i∈U⎛⎝ci+∑(i,j)∈E(q2ij−q1ij)⎞⎠+∑(i,j)∈E0(U)(q2ij−2q1ij+q0ij)+∑(i,j)∈E(2q1ij−q2ij), = g(U)+∑(i,j)∈E(2q1ij−q2ij).

Thus, for any feasible solution of GVC and the instance of GVC1 constructed above, is a constant. Therefore, an optimal solution to this GVC1 will also be an optimal solution to GVC.

Since GVC1 is a special case of GVC, any GVC1 can be formulated as GVC, establishing equivalence between GVC and GVC1.

To establish the equivalence between GVC and GVC2, define

 c′′i= ci+∑(i,j)∈E(q1ij−q0ij), ∀ i∈V and (6) q2′′ij= q2ij−2q1ij+q0ij, (i,j)∈E. (7)

Consider the instance of GVC2 where is replaced by and is replaced by . As in the previous case, we can show that an optimal solution to this GVC2 provides an optimal solution to GVC and the converse follows the fact that GVC2 is a special case of GVC.

###### Corollary 2.2.

GVC, GVC1, and GVC2 are NP-hard on complete graphs.

###### Proof.

This follows from Theorem 2.1 and the fact that GVC2-HB is NP-hard on complete graphs [7]. ∎

It may be noted that the special cases MWISP, MWVCP of GVC are trivial on a complete graph.

###### Theorem 2.3.

GVC, GVC1, and GVC2 are equivalent to UBQP.

###### Proof.

We first show that GVC2 can be formulated as UBQP. For any feasible solution , let and be the objective function values of GVC2, and UBQP respectively.

Define the matrix as

 qij=⎧⎪⎨⎪⎩q2ij2,∀(i,j)∈E,0 if (i,j)∉E. (8)

and

 ai=ci, ∀i∈V. (9)

Consider the UBQP with and as defined above. For any feasible solution of GVC2 or UBQP, . Thus an optimal solution to UBQP constructed above is also an optimal solution to GVC2.

To show that UBQP can be formulated as GVC2, let be the cost matrix of an instance of UBQP and be the support graph of . Choose , for edge of the support graph . Then, an optimal solution to the resulting GVC2 on solves UBQP. Thus GVC2 and UBQP are equivalent. The equivalence of GVC, GVC1, and UBQP now follow from Theorem 2.1. ∎

Although the equivalence of GVC, GVC1, GVC2 and UBQP are established in Theorem 2.3, the direct reformulation as a UBQP was given only for the GVC2. It is however interesting to present the precise structure of when GVC and GVC1 are reformulated as a UBQP. This is particularly useful in identifying polynomially solvable special cases directly from solvable UBQP instances. For any feasible solution , let and be the objective function values of GVC, GVC1, and UBQP respectively.

Define as

 qij=⎧⎪⎨⎪⎩q2ij−2q1ij+q0ij2,∀(i,j)∈E,0 if (i,j)∉E. (10)

and

 ai=ci+∑(i,j)∈E(q1ij−q0ij) ∀i∈V. (11)

Consider the UBQP with and are as defined above. For any ,

 f(U)=∑i∈Uci+∑(i,j)∈E0(U)q0ij+∑(i,j)∈E1(U)q1ij+∑(i,j)∈E2(U)q2ij. (12)

It can be verified that

 ∑(i,j)∈E0(U)q0ij = ∑(i,j)∈Eq0ij−∑(i,j)∈E,i∈Uq0ij−∑(i,j)∈E,j∈Uq0ij+∑(i,j)∈E2(U)q0ij % and (13) ∑(i,j)∈E1(U)q1ij = ∑(i,j)∈E,i∈Uq1ij+∑(i,j)∈E,j∈Uq1ij−∑(i,j)∈E2(U)q1ij. (14)

From (12), (13) and (14), we have

 f(U)= ∑i∈Uci+∑(i,j)∈Eq0ij−∑(i,j)∈E,i∈Uq0ij−∑(i,j)∈E,j∈Uq0ij+∑(i,j)∈E2(U)q0ij, +∑(i,j)∈E,i∈Uq1ij+∑(i,j)∈E,j∈Uq1ij−∑(i,j)∈E2(U)q1ij+∑(i,j)∈E2(U)q2ij, = ∑i∈U(ci+∑(i,j)∈E(q1ij−q0ij))+∑(i,j)∈E2(U)(q2ij−2q1ij+q0ij)+∑(i,j)∈Eq0ij, = ∑i∈Uai+∑(i,j)∈E2(U)2qij+∑(i,j)∈Eq0ij, = ϕ(U)+∑(i,j)∈Eq0ij. (15)

Thus an optimal solution to the UBQP constructed above is also an optimal solution to GVC.

Now, define the matrix as

 qij=⎧⎪⎨⎪⎩q0ij2,∀(i,j)∈E,0 if (i,j)∉E. (16)

and

 ai=ci−∑(i,j)∈Eq0ij, ∀i∈V. (17)

Consider an instance of UBQP with and as defined above.

Then

 g(U) = ∑i∈Uci+∑(i,j)∈E0(U)q0ij, = ∑i∈Uci+∑(i,j)∈Eq0ij−∑(i,j)∈E,i∈Uq0ij−∑(i,j)∈E,j∈Uq0ij+∑(i,j)∈E2(U)q0ij, = ∑i∈U(ci−∑(i,j)∈Eq0ij)+∑(i,j)∈E2(U)q0ij+∑(i,j)∈Eq0ij, = ϕ(U)+∑(i,j)∈Eq0ij.

Thus an optimal solution to this UBQP is an optimal solution to GVC1.

Let be the matrix defined as in equation (10) and as in equation (11).

###### Corollary 2.4.
• GVC is polynomial-time solvable on a series-parallel graph .

• If the rank of is fixed and is a positive semi-definite, then GVC is polynomial-time solvable.

• If and are non-negative, then GVC is polynomial-time solvable.

• GVC is polynomial-time solvable if , where is defined in equation (10).

###### Proof.

From the construction given in equation (15), the support graph of is a subgraph of on which GVC is defined. Note that UBQP is solvable in polynomial time if the support graph of the cost matrix is series-parallel [5, 22]. Since any subgraph of a series-parallel graph is series-parallel, the result follows.

If the rank of is fixed and is a positive semi-definite, then UBQP is polynomial time solvable [2, 11, 18, 22], and if and are non-negative, UBQP is polynomial time solvable [22]. The result now follows from Theorem 2.3.

When , where is defined in equation (10), Picard et al. [28, 29] showed that UBQP can be reduced to minimum-cut problem on the graph , where , denotes the source and the sink, and with [22]. Therefore, in this case GVC is equivalent to the minimum-cut problem which is polynomial time solvable [28, 29].

Similar results follow for GVC2 if is defined as in (8) and is defined as in equation (9) and for GVC1 when if is defined as in (16) and is defined as in equation (17).

It may be noted that the reductions discussed in Theorem 2.1 and 2.3 above for GVC and GVC1 to UBQP do not preserve -optimality because of the resulting constant terms in the objective function. However, for GVC2, reduction to UBQP preserves -optimality. The equivalence however preserves other performance measures such as differential approximation ratio [3, 9] and domination ratio [12].

For any graph and , is the graph obtained by deleting node and all its incident edges. Then GVC2 on can be solved by solving GVC2 on with two different data sets. Note that in an optimal solution to GVC2 on , either belongs or does not belongs to an optimal solution. If does not belong, then any optimal solution to GVC2 on with original data (restricted to nodes and edges of ) is also an optimal solution to GVC2 on . Otherwise, define

 c′i={ci+q2iv,∀i∈δ(v),ci otherwise

and for all edge in , where .

Let be an optimal solution to GVC2 on with replaced by and is replaced by . Also let be an optimal solution to GVC2 on with original data. Then the best of will be an optimal solution to GVC2 on . This idea (together with Theorem 2.1) can be applied recursively to establish the following.

###### Theorem 2.5.

GVC, GVC1, and GVC2 can be solved in polynomial time on if GVC2 can be solved in polynomial time on for some where .

It is well known that if is an optimal vertex cover then is an optimal independent set. A similar relationship exist between GVC1 and GVC2.

###### Lemma 2.6.

is an optimal solution to GVC1 with data and if and only if is an optimal solution to GVC2 with data and

###### Proof.

Suppose is an optimal solution to the GVC1. Then for any

 ∑i∈U0ci+∑(i,j)∈E0(U0)q0ij ≤∑i∈Uci+∑(i,j)∈E0(U)q0ij. (18)

Consider the objective function value of the GVC2 given in the statement of the lemma for the solution . We have,

 ∑i∈(V−U0)−ci+∑(i,j)∈E2(V−U0)q2ij =∑i∈V−ci−∑i∈U0−ci+∑(i,j)∈E0(U0)q2ij, =∑i∈V−ci+∑i∈U0ci+∑(i,j)∈E0(U0)q0ij, ≤∑i∈V−ci+∑i∈Uci+∑(i,j)∈E0(U)q0ij, ∀U⊆V from (???), ≤∑i∈(V−U)−ci+∑(i,j)∈E2(V−U)q2ij, ∀U⊆V.

Since any subset of can be represented as , for , it follows that is an optimal solution to GVC2 defined above. The converse can be proved analogously. ∎

### 2.1 Bipartite graphs

Bipartite graph is a subclass of perfect graphs on which the MWVCP and MWISP can be solved in polynomial time [33]. Houchbaum [16] and Bar-Yehuda et al.  [7] showed that GVC1-HB solvable in polynomial time on bipartite graphs. Hochbaum and Pathria [15] showed that GVC1-HP is solvable in polynomial time on bipartite graphs. Thus it is interesting to investigate the complexity of GVC, GVC1, and GVC2 on bipartite graphs. Let us first define these problems on bipartite graphs using the bi-partitioned structure of the vertex set.

Let be a bipartite graph, where , and . For each vertex a weight is prescribed and for each vertex a weight is prescribed. Let , , , and . Then GVC on this bipartite graph is to find such that

 f(U1,U2)=∑i∈U1ci+∑j∈U2dj+∑(i,j)∈E0(U1,U2)q0ij+∑(i,j)∈E1(U1,U2)q1ij+∑(i,j)∈E2(U1,U2)q2ij,

is minimized. Similarly, GVC1 is to minimize

 g(U1,U2)=∑i∈U1ci+∑j∈U2dj+∑(i,j)∈E0(U1,U2)q0ij,

and GVC2 is to minimize

 h(U1,U2)=∑i∈U1ci+∑j∈U2dj+∑(i,j)∈E2(U1,U2)q2ij.

Without loss of generality we assume .

###### Observation 2.7.

GVC is solvable in polynomial time on bipartite graphs if and or and .

###### Proof.

If the first set of conditions are satisfied, then from Theorem 2.1, GVC reduces to GVC1-HB, which is solvable in polynomial time on bipartite graphs [7]. If the second set of conditions are satisfied, then GVC reduces to GVC2-HP, which is solvable in polynomial time on bipartite graphs [15]. ∎

###### Theorem 2.8.

GVC, GVC1, and GVC2 on bipartite graphs are equivalent to BQP01.

###### Proof.

For any feasible solution , where and , let and be the objective function values of GVC2, and BQP01 respectively.

Define the matrix as

 qij={q2ij,∀(i,j)∈E,0 if (i,j)∉E. (19)

Set and . Consider the BQP01 with , and are as defined above. For any feasible solution


text:
# What Are the Power Rules for Variables?

It is very important to know the six rules of powers, or exponentiation. Here, we’ll go through each of them and you’ll see why they work. Rules 1 and 2 are presented in this entry, followed by Rules 3 and 4, about dividing powers, and Rules 5 and 6, about powers of parentheses. At the end, you will find some examples where you’ll have to use several of the rules at the same time.

There’s no reason to be afraid of these. As long as you make sure to follow the rules, you’ll always end up in the right place. That’s why one of the first steps you should take is to memorize these six rules! But first, let’s examine what powers look like.

Rule

### Powers

The expression ${a}^{b}$ is called a power.

$a$ is called the base.

$b$ is called the exponent.

Rule

### TothePower0

Anything with an exponent of 0 equals 1, as long as $a\ne 0$ (${0}^{0}$ is undefined).

 ${a}^{0}=1$

Example 1

Here are a couple of different examples of 0 being the exponent, showing that the answer is always 1.

 $27{5}^{0}={1}^{0}={x}^{0}=5.{6}^{0}={y}^{0}=1$

Rule

### MultiplyingTwoPowerswiththeSameBase

 ${a}^{m}\cdot {a}^{n}={a}^{m+n}$

Let’s have a look at how this must be true with the help of an example:

 ${a}^{3}=a\cdot a\cdot a$

and

 ${a}^{4}=a\cdot a\cdot a\cdot a$

This means that $\begin{array}{llll}\hfill {a}^{3}\cdot {a}^{4}& =\underset{{a}^{3}}{\underbrace{a\cdot a\cdot a}}\cdot \underset{{a}^{4}}{\underbrace{a\cdot a\cdot a\cdot a}}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & =a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & ={a}^{3+4}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & ={a}^{7}.\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$

This rule is very important to memorize. Here are some more examples:

Example 2

Simplify ${x}^{3}\cdot {x}^{4}$ as much as possible

 ${x}^{3}\cdot {x}^{4}={x}^{3+4}={x}^{7}$

Simplify ${a}^{-2}\cdot {a}^{5}$ as much as possible

 ${a}^{-2}\cdot {a}^{5}={a}^{-2+5}={a}^{3}$

Simplify ${b}^{-7}\cdot {b}^{-13}$ as much as possible

$\begin{array}{llll}\hfill {b}^{-7}\cdot {b}^{-13}& ={b}^{-7+\left(-13\right)}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & ={b}^{-7-13}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\\ \hfill & ={b}^{-20}\phantom{\rule{2em}{0ex}}& \hfill & \phantom{\rule{2em}{0ex}}\end{array}$


text:
# Bernstein Inequality for continous local martingale

I'm looking for a simple proof of the following fact, which is somehow Bernstein inequality in continuous time.

Let $$(M_t)_{t\geq 0}$$ be a continuous local martingale. Then :

$$P\left(\sup_{t\in [0,T]}M_t \geq a \ \vert \ [M]_T\leq b\right) \leq \exp\left(-\frac{a^2}{2b}\right).$$

It's a special case of an inequality of Shorack and Wellner, but I think there should be an easy proof. One can use Dubins-Schwarz theorem but I don't want to, I'm looking for a direct proof, in the spirit of Bernstein Inequality.


text:
# Python Ridge Regression¶

## A Basic Example Using the Boston House Prices Dataset¶

### Overview¶

Linear regression (i.e. ordinary least squares) is one of the most commonly used statistical modeling technique. It works wonderfully in many situations, but there are scenarios in which some other version of linear modeling could yield a better answer.

In this example, we turn to something called "Ridge" regression. We will not go into the mathematical details of this model. A few resources are listed below if you are interested in a deeper dive.

I will note that Ridge does not always outperform linear regression. However, there is a chance of it performing better (on test data) in cases where there is a significant amount of multicollinearity present. Ridge regression does not perform variable selection. However, it 'shrinks' the coefficients towards zero. Linear regression has low bias (actually, zero bias), with Ridge, we are aiming to trade-off some increase in bias towards decreased variance.

### Data Exploration¶

First we import a the boston house prices dataset, and print a description of it so we can examine what is in the data. Remember in order to execute a 'cell' like the one below, you can 1) click on it and run it using the run button above or 2) click in the cell and hit shift+enter.

In [1]:
import pandas as pd
print(boston.data.shape) #get (numer of rows, number of columns or 'features')
print(boston.DESCR) #get a description of the dataset

(506, 13)
.. _boston_dataset:

Boston house prices dataset
---------------------------

**Data Set Characteristics:**

:Number of Instances: 506

:Number of Attributes: 13 numeric/categorical predictive. Median Value (attribute 14) is usually the target.

:Attribute Information (in order):
- CRIM     per capita crime rate by town
- ZN       proportion of residential land zoned for lots over 25,000 sq.ft.
- INDUS    proportion of non-retail business acres per town
- CHAS     Charles River dummy variable (= 1 if tract bounds river; 0 otherwise)
- NOX      nitric oxides concentration (parts per 10 million)
- RM       average number of rooms per dwelling
- AGE      proportion of owner-occupied units built prior to 1940
- DIS      weighted distances to five Boston employment centres
- TAX      full-value property-tax rate per $10,000 - PTRATIO pupil-teacher ratio by town - B 1000(Bk - 0.63)^2 where Bk is the proportion of blacks by town - LSTAT % lower status of the population - MEDV Median value of owner-occupied homes in$1000's

:Missing Attribute Values: None

:Creator: Harrison, D. and Rubinfeld, D.L.

This is a copy of UCI ML housing dataset.
https://archive.ics.uci.edu/ml/machine-learning-databases/housing/

This dataset was taken from the StatLib library which is maintained at Carnegie Mellon University.

The Boston house-price data of Harrison, D. and Rubinfeld, D.L. 'Hedonic
prices and the demand for clean air', J. Environ. Economics & Management,
vol.5, 81-102, 1978.   Used in Belsley, Kuh & Welsch, 'Regression diagnostics
...', Wiley, 1980.   N.B. Various transformations are used in the table on
pages 244-261 of the latter.

The Boston house-price data has been used in many machine learning papers that address regression
problems.

.. topic:: References

- Belsley, Kuh & Welsch, 'Regression diagnostics: Identifying Influential Data and Sources of Collinearity', Wiley, 1980. 244-261.
- Quinlan,R. (1993). Combining Instance-Based and Model-Based Learning. In Proceedings on the Tenth International Conference of Machine Learning, 236-243, University of Massachusetts, Amherst. Morgan Kaufmann.

In [2]:
data = pd.DataFrame(boston.data, columns=boston.feature_names)

Out[2]:
CRIM ZN INDUS CHAS NOX RM AGE DIS RAD TAX PTRATIO B LSTAT
0 0.00632 18.0 2.31 0.0 0.538 6.575 65.2 4.0900 1.0 296.0 15.3 396.90 4.98
1 0.02731 0.0 7.07 0.0 0.469 6.421 78.9 4.9671 2.0 242.0 17.8 396.90 9.14
2 0.02729 0.0 7.07 0.0 0.469 7.185 61.1 4.9671 2.0 242.0 17.8 392.83 4.03
3 0.03237 0.0 2.18 0.0 0.458 6.998 45.8 6.0622 3.0 222.0 18.7 394.63 2.94
4 0.06905 0.0 2.18 0.0 0.458 7.147 54.2 6.0622 3.0 222.0 18.7 396.90 5.33
In [5]:
#For some reason, the loaded data does not include the target variable (MEDV), we add it here
data['MEDV'] = pd.Series(data=boston.target, index=data.index)
data.describe() #get some basic stats on the dataset

Out[5]:
CRIM ZN INDUS CHAS NOX RM AGE DIS RAD TAX PTRATIO B LSTAT MEDV
count 506.000000 506.000000 506.000000 506.000000 506.000000 506.000000 506.000000 506.000000 506.000000 506.000000 506.000000 506.000000 506.000000 506.000000
mean 3.613524 11.363636 11.136779 0.069170 0.554695 6.284634 68.574901 3.795043 9.549407 408.237154 18.455534 356.674032 12.653063 22.532806
std 8.601545 23.322453 6.860353 0.253994 0.115878 0.702617 28.148861 2.105710 8.707259 168.537116 2.164946 91.294864 7.141062 9.197104
min 0.006320 0.000000 0.460000 0.000000 0.385000 3.561000 2.900000 1.129600 1.000000 187.000000 12.600000 0.320000 1.730000 5.000000
25% 0.082045 0.000000 5.190000 0.000000 0.449000 5.885500 45.025000 2.100175 4.000000 279.000000 17.400000 375.377500 6.950000 17.025000
50% 0.256510 0.000000 9.690000 0.000000 0.538000 6.208500 77.500000 3.207450 5.000000 330.000000 19.050000 391.440000 11.360000 21.200000
75% 3.677083 12.500000 18.100000 0.000000 0.624000 6.623500 94.075000 5.188425 24.000000 666.000000 20.200000 396.225000 16.955000 25.000000
max 88.976200 100.000000 27.740000 1.000000 0.871000 8.780000 100.000000 12.126500 24.000000 711.000000 22.000000 396.900000 37.970000 50.000000
In [6]:
#Load the independent variables (the x1, x2, etc.) into a dataframe object called 'X'. Similarly for the dependent variable 'Y'
X = data.drop('MEDV', axis = 1) #define independent predictor set (excluding the dependent variable)
Y = data['MEDV'] #define the target values (i.e. the dependent variable)

We randomly select a third of our data to be the 'test' dataset. This way we can train our model on 2/3 of the data, and test it on the remainder. Once we are confident that our model is generalizing well (i.e. there is not a HUGE different in the training/testing performance, or in other words, not obviously overfitting), then we can use all of our data to train the model.

In [7]:
from sklearn.model_selection import train_test_split
X_train, X_test, Y_train, Y_test = train_test_split(X, Y, test_size = 0.33, random_state = 5)
print(X_train.shape)
print(X_test.shape)
print(Y_train.shape)
print(Y_test.shape)

(339, 13)
(167, 13)
(339,)
(167,)

### Ridge Regression¶

We now import the 'Ridge' method from the sklearn library, and the fit our model as follows:

In [9]:
from sklearn.linear_model import Ridge
rr = Ridge(alpha=1) #a higher value of alpha restricts the coefficients further
rr.fit(X_train,Y_train)
Y_pred_train = rr.predict(X_train) #predictions on training data
Y_pred = rr.predict(X_test) #predictions on testing data
# We plot predicted Y (y-axis) against actual Y (x-axis). Perfect predictions will lie on the diagonal. We see the diagonal trend, suggesting a 'good' fit
import matplotlib.pyplot as plt
plt.scatter(Y_test,Y_pred)
plt.xlabel("Actual Price: $Y_i$")
plt.ylabel("Predicted Price: $\hat{Y}_i$")
plt.title("Predicted Price vs Actual Price: $Y_i$ vs $\hat{Y}_i$")
plt.show()

In [10]:
from sklearn.metrics import mean_squared_error, r2_score
mse = mean_squared_error(Y_test,Y_pred)
print('Mean Squared Error: ',mse)
rsq = r2_score(Y_train,Y_pred_train)
print('R-square, Training: ',rsq)
rsq = r2_score(Y_test,Y_pred)
print('R-square, Testing: ',rsq)

Mean Squared Error:  29.294062013484965
R-square, Training:  0.7535758947696942
R-square, Testing:  0.6875095305967148

In [11]:
#Let's get the coefficients
print('Intercept: ',rr.intercept_) # This gives us the intercept term
print('Coefficients: \n',rr.coef_) # This gives us the coefficients (in the case of this model, just one coefficient)

Intercept:  28.880383249855868
Coefficients:
[-0.15284685  0.0397696  -0.05156612  0.63428674 -6.35714924  4.00925859
-0.01709152 -1.27297943  0.32788793 -0.0143354  -0.92053665  0.01186824
-0.48449948]

You can compare this example to the OLS method: https://predictivemodeler.com/2019/08/19/py-ols-boston-house-prices/

### Feedback¶

If you have ideas on how to improve this post, please let me know: https://predictivemodeler.com/feedback/