Using orthogonally structured positive bases for constructing positive $k$-spanning sets with cosine measure guarantees

In this section, we recall the definitions of positive spanning sets and positive bases, based on the seminal paper of Davis [4].

When $\mathbb{L}$ is not specified, a positive spanning set is understood as positively spanning $\mathbb{R}^{n}$. Throughout the paper, we only consider positive spanning sets formed of nonzero vectors. Note, however, that we do not force all elements of a positive spanning set to be distinct. The next two lemmas are well known and describe basic properties of positive spanning sets.

Note that Lemma 2.2 implies that a PSS must contain at least $\dim(\mathbb{L})+1$ vectors. There is no upper bound on the number of elements that a PSS may contain, but such a restriction holds for a subclass of positive spanning sets called positive bases.

In other words, positive bases of $\mathbb{L}$ are inclusion-wise minimal positive spanning sets of $\mathbb{L}$ [3]. Positive bases can also be defined thanks to the notion of positive independence.

A positive basis of $\mathbb{L}$ is thus a positively independent PSS of $\mathbb{L}$.In the case $\mathbb{L}=\mathbb{R}^{n}$, we simply say that $\mathcal{D}_{n,s}$ is a positive basis (of size $n+s$).

One can show that the size of a positive basis of a subspace $\mathbb{L}$ is at least $\dim(\mathbb{L})+1$ and at most $2\dim(\mathbb{L})$ [2, 4].

Maximal and minimal positive bases have a well-understood structure [2, 17]. The structure of an arbitrary positive basis can however be quite complicated to analyze. In the next section, we describe a decomposition formula for positive bases that identifies a favorable structure.

A complete characterization of positive bases can be provided through a subspace decomposition [21]. Such a decomposition is based upon the concept of critical vectors defined below.

Note that the zero vector is a critical vector for every positive basis of $\mathbb{L}$, and that it is the only critical vector for a maximal positive basis [21]. Moreover, if $\mathcal{D}_{\mathbb{L}}$ is a minimal positive basis and $\dim(\mathbb{L})\geq 2$, the set of critical vectors (known as the complete critical set) is given by

Using critical vectors, one may decompose any positive basis as a union of minimal positive bases. Theorem 2.1 gives the result for a positive basis in $\mathbb{R}^{n}$, by adapting the original decomposition result due to Romanowicz [21, Theorem 1] (see also [7, Lemma 25]).

The result of Theorem 2.1 is actually an equivalence, in that any set that admits the decomposition (1) is a non-minimal positive basis of $\mathbb{R}^{n}$ [21, Theorem 1]. The example below provides an illustration for both Definition 2.5 and Theorem 2.1. One can easily check that the stated vector is indeed critical, and that the proposed decomposition matches (1).

In general, however, the decomposition (1) is hard to compute, as it requires to determine the critical vectors and the subspaces $\mathbb{L}_{i}$, that need not be orthogonal to one another. These considerations have lead researchers to consider a subclass of positive bases with a nicer decomposition [7], leading to Definition 2.6 below.

By construction, note that for any $1\leq i<j\leq s$, any pair of elements $(\mathbf{d},\mathbf{d}^{\prime})\in\mathcal{D}_{\mathbb{L}_{i}}\times\mathcal{D}_{\mathbb{L}_{j}}$ satisfies $\mathbf{d}^{\top}\mathbf{d}^{\prime}=0$.

The class of orthogonally structured positive bases includes common positive bases, such as minimal ones and certain maximal positive bases such as those formed by the coordinate vectors and their negatives in $\mathbb{R}^{n}$. More OSPBs can be obtained via numerical procedures, even for intermediate sizes [7]. As will be shown in Section 3, it is also possible to compute their cosine measure in an efficient manner.

To end this background section, we define the cosine measure, a metric associated with a given family of vectors.

The cosine measure and cosine vector set provide insights on the geometry of the elements of $\mathcal{D}$ in the space. Such concepts are of particular interest in the case of positive spanning sets, as shown by the result of Proposition 2.1. Its proof can be found in key references in derivative-free optimization [2, 3], but note that our analysis in Section 4 provides a more general proof in the context of positive $k$-spanning sets.

Proposition 2.1 shows that the positive spanning property can be checked by computing the cosine measure. The value of the cosine measure further characterizes how well that set covers the space, which is a relevant information in derivative-free algorithms [10]. Both observations motivate the search for efficient techniques to compute the cosine measure.

We end this section by providing several examples of cosine measures for orthogonally structured positive bases, that form the core interest of this paper. We focus on building those positive bases from the coordinate vectors. A classical choice for a maximal positive basis consists in selecting the coordinate vectors and their negatives. In that case, it is known [16] that

One can also consider a minimal positive basis formed by the coordinate vectors and the sum of their negatives. Then, we have

To the best of our knowledge, the latter formula has only been recently established in [9, 20], and no formal proof is available in the literature. In the next section, we will develop an efficient cosine measure calculation technique for orthogonally structured positive bases that will provide a proof of this result as a byproduct.

The favorable structure of an OSPB can be revealed through the properties of its matrix representations, and in particular the Gram matrices associated with an OSPB, in the sense of Definition 3.1 below.

Given a Gram matrix $\mathbf{G}(\mathbf{S})$ of $\mathcal{S}$, any Gram matrix of $\mathcal{S}$ has the form $\mathbf{P}^{\top}\mathbf{G}(\mathbf{S})\mathbf{P}$ where $\mathbf{P}$ is a permutation matrix. We will show that when $\mathcal{S}$ is an OSPB, there exists a Gram matrix with a block-diagonal structure that reveals the decomposition of the basis, and thus its OSPB nature.

Proof. Suppose first that $\mathcal{D}_{n,s}$ is an OSPB associated to the decomposition

Let $\mathbf{D}_{n,s}$ be a matrix representation of $\mathcal{D}_{n,s}$ such that $\mathbf{D}_{n,s}=\begin{bmatrix}\mathbf{D}_{\mathbb{L}_{1}}&\cdots&\mathbf{D}_{\mathbb{L}_{s}}\end{bmatrix}$, where $\mathbf{D}_{\mathbb{L}_{i}}$ is a matrix representation of $\mathcal{D}_{\mathbb{L}_{i}}$ for every $i\in[\![1,s]\!]$. By orthogonality of those matrices, the Gram matrix $\mathbf{G}(\mathbf{D}_{n,s})=\mathbf{D}_{n,s}^{\top}\mathbf{D}_{n,s}$ is then block diagonal with $s$ blocks corresponding to $\mathbf{G}(\mathbf{D}_{\mathbb{L}_{1}}),\dots,\mathbf{G}(\mathbf{D}_{\mathbb{L}_{s}})$, and thus the desired result holds.

Conversely, suppose that there exists a matrix representation $\mathbf{D}_{n,s}$ of $\mathcal{D}_{n,s}$ such that $\mathbf{G}(\mathbf{D}_{n,s})$ is block diagonal with $s$ blocks. Then, by considering a partitioning with respect to those diagonal blocks, one can decompose $\mathbf{D}_{n,s}$ into $\begin{bmatrix}\mathbf{S}_{1}&\cdots&\mathbf{S}_{s}\end{bmatrix}$ so that $\mathbf{G}(\mathbf{D}_{n,s})=\operatorname{diag}\left(\mathbf{G}(\mathbf{S}_{1}),\dots,\mathbf{G}(\mathbf{S}_{s})\right)$. By definition of the Gram matrix, this structure implies that the columns of $\mathbf{S}_{i}$ and $\mathbf{S}_{j}$ are orthogonal for any $i\neq j$, thus we only need to show that each $\mathbf{S}_{i}$ is a minimal positive basis for its linear span. To this end, we use the fact that $\mathcal{D}_{n,s}$ is positively spanning. By Lemma 2.1(ii), there exists a vector $\mathbf{u}\in\mathbb{R}^{n+s}$ with positive coefficients such that $\mathbf{D}_{n,s}\mathbf{u}=\mathbf{0}_{n}$. By decomposing the vector $\mathbf{u}$ into $s$ vectors $\mathbf{u}_{1},\dots,\mathbf{u}_{s}$ according to the decomposition $\begin{bmatrix}\mathbf{S}_{1}&\cdots&\mathbf{S}_{s}\end{bmatrix}$, we obtain that

By orthogonality of the columns of the $\mathbf{S}_{i}$ matrices, the property (3) is equivalent to

Using again Lemma 2.1(ii), this latter property is equivalent to $\mathcal{S}_{i}$ being a PSS for its linear span. Let $n_{i}$ be the dimension of this span, and $m_{i}$ the number of elements in $\mathcal{S}_{i}$. Since the $\mathbf{S}_{i}$ are orthogonal and the columns of $\mathbf{D}_{n,s}$ span $\mathbb{R}^{n}$, we must have $\sum_{i=1}^{s}n_{i}=n$. In addition, we also have $\sum_{i=1}^{s}m_{i}=n+s=\sum_{i=1}^{s}n_{i}+s$. Since $m_{i}>n_{i}$ for all $i\in[\![1,s]\!]$, we conclude that $m_{i}=n_{i}+1$, and thus every $\mathcal{S}_{i}$ is a minimal positive basis. $\Box$

Note that the characterization stated by Theorem 3.1 trivially holds for minimal positive bases. This theorem thus provides a characterization of the OSPB property through Gram matrices. One can then use this result to determine whether a positive basis has an orthogonal structure and, in that event, to highlight the associated decomposition.

Corollary 3.1 provides a principled way of detecting the OSPB structure, by checking all possible permutations of the elements in the basis. Although this is not the focus of this work, we remark that it can be done in an efficient manner by considering a graph whose Laplacian matrix $\mathbf{L}$ has non-zero coordinates in the exact same rows and columns as $\mathbf{G}(\mathbf{D}_{n,s})$. Indeed, the problem of finding the permutation for matrix $\mathbf{L}$ reduces to that of finding the number of connected components in the graph [14] and can be solved in polynomial time [8].

As seen in the previous section, orthogonally structured positive bases admit a decomposition into minimal positive bases that are orthogonal to one another. In this section, we investigate how this particular structure allows for efficient computation of the cosine measure.

Our approach builds on the algorithm introduced by Hare and Jarry-Bolduc [6], that computes the cosine measure of any positive spanning set in finite time (though the computation time may be exponential in the problem dimension). This procedure consists of a loop over all possible linear bases contained in the positive spanning set. More formally, given a positive spanning set $\mathcal{D}$ in $\mathbb{R}^{n}$ and a linear basis $\mathcal{B}\subset\mathcal{D}$, we let $\mathbf{D}$ be a matrix representation of $\mathcal{D}$, and $\mathbf{B}$ the associated representation of $\mathcal{B}$. One then defines

The vector $\mathbf{u}_{\mathcal{B}}$ is the only unitary vector such that $\mathbf{u}_{\mathcal{B}}^{\top}\tfrac{\mathbf{d}}{\|\mathbf{d}\|}=\gamma_{\mathcal{B}}$ for all $\mathbf{d}\in\mathcal{B}$ [6, Lemmas 12 and 13]. Computing the quantities (4) for all linear bases contained in $\mathcal{D}$ then gives both the cosine measure and the cosine vector set for $\mathcal{D}$ [6, Theorem 19]. Indeed, we have

while the cosine vector set is given by

The next proposition shows how, when dealing with OSPBs, formula (5) can be simplified to give a more direct link between the quantities $\gamma_{\mathcal{B}}$ and the cosine measure.

Proof. Using the decomposition of $\mathcal{D}_{n,s}$, any linear basis $\mathcal{B}_{n}$ of $\mathbb{R}^{n}$ contained in $\mathcal{D}_{n,s}$ can be decomposed as $\mathcal{B}_{n}=\mathcal{B}_{\mathbb{L}_{1}}\cup\cdots\cup\mathcal{B}_{\mathbb{L}_{s}}$ where $\mathcal{B}_{\mathbb{L}_{i}}\subset\mathcal{D}_{\mathbb{L}_{i}}$ is a linear basis of $\mathbb{L}_{i}$. By construction, the vector $\mathbf{u}_{\mathcal{B}_{n}}$ makes a positive dot product with every element of $\mathcal{B}_{n}$ (and thus with every element of any $\mathcal{B}_{\mathbb{L}_{i}}$) equal to $\gamma_{\mathcal{B}_{n}}$. Consequently, the vector $\mathbf{u}_{\mathcal{B}_{n}}$ lies in the positive span of $\mathcal{B}_{n}$, and its projection on any subspace $\mathbb{L}_{i}$ lies in the positive span of $\mathcal{B}_{\mathbb{L}_{i}}$.

Meanwhile, for any $i\in[\![1,s]\!]$, there exists $\mathbf{d}_{i}\in\mathcal{D}_{\mathbb{L}_{i}}$ such that $\mathcal{B}_{\mathbb{L}_{i}}=\mathcal{D}_{\mathbb{L}_{i}}\setminus\{\mathbf{d}_{i}\}$, and this vector satisfies $\mathbf{u}_{\mathcal{B}_{n}}^{\top}\mathbf{d}_{i}<0$ per Lemma 2.1$(\ref{lem: PSS eq pos dotprod})$, leading to

where the second equality comes from $\mathbf{u}_{\mathcal{B}_{n}}^{\top}\mathbf{d}_{i}<0$ and $\max\limits_{\mathbf{d}\in\mathcal{D}_{n}}\mathbf{u}_{\mathcal{B}_{n}}^{\top}\mathbf{d}>0$, and the last equality holds by definition of $\gamma_{\mathcal{B}_{n}}$. Recalling that $\operatorname{cm}\left(\mathcal{D}_{n}\right)$ is given by (5) concludes the proof. $\Box$

One drawback of the approach described so far is that it requires computing the quantities (4) for all linear bases including in the positive spanning set of interest. In the case of OSPBs, we show below that the number of linear bases to be considered can be greatly reduced by leveraging to their decomposition into minimal positive bases.

Proof. Let $\mathbf{B}_{n}$ be a matrix representation of $\mathcal{B}_{n}$ such that $\mathbf{B}_{n}=\begin{bmatrix}\mathbf{B}_{\mathbb{L}_{1}}\cdots\mathbf{B}_{\mathbb{L}_{s}}\end{bmatrix}$. Then, the Gram matrix of $\mathbf{B}_{n}$ is $\mathbf{G}(\mathbf{B}_{n})=\operatorname{diag}\left(\mathbf{G}(\mathbf{B}_{\mathbb{L}_{1}}),\dots,\mathbf{G}(\mathbf{B}_{\mathbb{L}_{s}})\right)$, implying that

which proves (6).

Recall now that every linear basis $\mathcal{B}_{\mathbb{L}_{i}}$ can be written as $\mathcal{D}_{\mathbb{L}_{i}}\setminus\{\mathbf{d}_{i}\}$ for some $\mathbf{d}_{i}\in\mathcal{D}_{\mathbb{L}_{i}}$. Combining this property together with (6) and Proposition 3.1, we obtain

proving (7).

Finally, combining (7) with the result of Proposition 3.1 on the cosine vector set gives

Using a matrix representation $\mathbf{B}_{n}=\begin{bmatrix}\mathbf{B}_{\mathbb{L}_{1}}\cdots\mathbf{B}_{\mathbb{L}_{s}}\end{bmatrix}$ along with the formula (4) for $\mathbf{u}_{\mathcal{B}_{n}}$ leads to

which is precisely (8). $\Box$

On a broader level, Theorem 3.2 shows that any calculation for a linear basis contained in an OSPB reduces to calculations on bases contained in each of the minimal positive bases in its decomposition. This observation leads to a principled way of computing the cosine measure from the OSPB decomposition, as described in Algorithm 1.

In essence, Algorithm 1 is quite similar to the generic method proposed for positive spanning sets [6]. However, Algorithm 1 reduces the computation of the cosine measure to that over minimal positive bases, which leads to significantly cheaper calculations. Indeed, for any minimal positive basis $\mathcal{D}_{\mathbb{L}_{i}}$ involved in the decomposition, the algorithm considers $|\mathcal{D}_{\mathbb{L}_{i}}|$ positive bases, and computes the quantities of interest (4) for each of those (which amounts to inverting or solving a linear system involving the associated Gram matrix). Overall, Algorithm 1 thus checks $\sum_{i=1}^{s}|\mathcal{D}_{\mathbb{L}_{i}}|=|\mathcal{D}_{n,s}|=n+s$ bases to compute the cosine measure (9). This result represents a significant improvement over the $\binom{n+s}{n}$ possible bases that are potentially required when the OSPB decomposition is not exploited, as in the algorithm for generic PSSs [6]. We also recall from Section 3.1 that Step 1 in Algorithm 1 can be performed in polynomial time.

To end this section, we illustrate how Algorithm 1 results in a straightforward calculation in the case of some minimal positive bases, by computing explicitly the cosine measure of the minimal positive basis $\mathcal{I}_{n}\cup\{-\mathbf{1}_{n}\}$. In this case, the calculation becomes easy thanks to the orthogonality of the vectors within $\mathcal{I}_{n}\cup\{-\mathbf{1}\}$. Although the value (10) was recently stated [9, 20] and checked numerically using the method of Hare and Jarry-Bolduc [6], to the best of our knowledge the formal proof below is new.

Proof. For the sake of simplicity, we normalize the last vector in the set (which does not change the value of the cosine measure) and we let $\mathcal{D}_{n}=\mathcal{I}_{n}\cup\{-\tfrac{1}{\sqrt{n}}\mathbf{1}_{n}\}$ in the rest of the proof. Since $\mathcal{D}_{n}$ is a positive basis, it follows that

Two cases are to be considered. Suppose first that $\mathbf{d}=-\tfrac{1}{\sqrt{n}}\mathbf{1}_{n}$, so that $\mathcal{D}_{n}\setminus\{\mathbf{d}\}=\mathcal{I}_{n}$. Then, any matrix representation of that basis $\mathbf{B}$ is such that $\mathbf{G}(\mathbf{B})=\mathbf{I}_{n}$. Consequently,

Suppose now that $\mathbf{d}=\mathbf{e}_{i}$ for some $i\in[\![1,n]\!]$. In that case, considering the matrix representation $\mathbf{B}_{i}=\begin{bmatrix}\mathbf{e}_{1}&\cdots&\mathbf{e}_{i-1}&\mathbf{e}_{i+1}&\cdots&\mathbf{e}_{n}&-\tfrac{1}{\sqrt{n}}\mathbf{1}_{n}\end{bmatrix}$, we obtain that

Since these formulas do not depend on $i$, we obtain that for all $i\in[\![1,n]\!]$, we have

Summing all coefficients of $\mathbf{G}(\mathbf{B}_{i})^{-1}$ gives $n-1+(n-1)^{2}+2(n-1)\sqrt{n}+n=n^{2}+2(n-1)\sqrt{n}$, hence $\gamma_{\mathcal{D}_{n}\setminus\{\mathbf{e}_{i}\}}=\frac{1}{\sqrt{n^{2}+2(n-1)\sqrt{n}}}$. Comparing this value with $\tfrac{1}{\sqrt{n}}$ yields the desired conclusion. $\Box$

Algorithm 1 allows for efficient calculation of cosine measures for specific positive spanning sets that originate from OSPBs, as we will establish in Section 4 in the case of positive $k$-spanning sets.

Our goal for this section is to provide a summary of results on positive $k$-spanning sets that mimic the standard ones for positive spanning sets. We start by defining the property of interest.

As for Definition 2.1, when $\mathbb{L}$ is not specified, a P$k$SS should be understood as a P$k$SS of $\mathbb{R}^{n}$. By construction, any P$k$SS of $\mathbb{L}$ must contain a PSS of $\mathbb{L}$, and therefore is a PSS of $\mathbb{L}$ itself. Moreover, the notions of positive $k$-span and P$k$SS with $k=1$ coincide with that of positive span and PSS from Definition 2.1. Similar to PSSs, we will omit the subspace of interest when $\mathbb{L}=\mathbb{R}^{n}$.

The notion of positive spanning set is inherently connected to that of spanning set, a standard concept in linear algebra. We provide below a counterpart notion associated with P$k$SSs.

Using the two definitions above, we can generalize the results of Lemma 2.1 and Lemma 2.2 to positive $k$-spanning sets. The proof is omitted as it merely amounts to combining the definitions with these two lemmas.