Generalized convex combination using matrices

524 Views Asked by At

A convex combination between two points $x_1$ and $x_2$ in $\mathbb{R}^N$ is defined as:

$$ x(\lambda) = \lambda x_1 + (1-\lambda)x_2, \qquad \lambda \in [0,1].$$

Here $x(0) = x_2$, $x(1) = x_1$, and the set $x(\lambda)$ (when $\lambda$ varies) can be interpreted as the line segment between $x_1$ and $x_2$, which is itself a convex set.

This could be generalized to matrix combinations, for example:

$$ x(A) = A x_1 + (I-A)x_2, \qquad 0 \preceq A \preceq I,$$

where $I$ is the identity matrix, $A \preceq B \Leftrightarrow B-A$ positive semi-definite, and similarly here $x(0) = x_2$ and $x(I) = x_1$.

Question: what can be said about the set $S = \{A x_1 + (I-A)x_2 | 0 \preceq A \preceq I\}$? In particular, is there any geometrical interpretation of S?

More generally, for $M$ point $\{x_i\}_{1,...,M}$, one could consider: $$\left\{\sum_{i=1}^M A_ix_i \;\Bigg| \;\sum_{i=1}^M A_i = I, \, \quad 0 \preceq A_i \preceq I\right\},$$ which simplifies to the convex hull of $\{x_i\}_{1,...,M}$ when $A_i = \lambda_i I$, $\sum \lambda_i = 1$

1

There are 1 best solutions below

0
On

Let $$[x, y] = \{Ax + (I-A)y : 0 \preceq A \preceq I\}.$$ So, as I conjectured in the comments, $$[x, y] = \left\{z \in \mathbb{R}^N : y \cdot (x - y) \le z \cdot (x - y) \le x \cdot (x - y)\right\},$$ which is the region between two hyperplanes perpendicular to the vector $y - x$. To see geometrically why this is true, consider the condition for $0 \preceq A$, which is to say that $v^\top A v \ge 0$ for all column vectors $v$, or equivalently, $v \cdot (Av) \ge 0$. That is, the angle between $v$ and $Av$ must remain acute (or orthogonal).

Similarly, since $I - A \succeq 0$, the angle between $v - Av$ and $v$ is at most $\pi/2$.

To prove it, fix $A$ such that $0 \preceq A \preceq I$, and let $$z = Ax + (I - A)y = y + A(x - y) = x + (I - A)(y - x).$$ Then, $$(x - y)^\top z = (x - y)^\top y + (x - y)^\top A (x - y) \ge (x - y)^\top y.$$ On the other hand, $$(x - y)^\top z = (x - y)^\top x - (x - y)^\top (I - A)(x - y) \le (x - y)^\top x.$$ Therefore, as required, $$y \cdot (x - y) \le z \cdot (x - y) \le x \cdot (x - y).\tag{$1$}$$ It remains to prove the converse. Fix a $z$ that satisfies $(1)$. Find an orthonormal basis for $\mathbb{R}^N$ starting with $\frac{x - y}{\|x - y\|}$: $$\mathcal{E} = \left(e_1 = \frac{x - y}{\|x - y\|}, e_2, e_3, \ldots, e_N\right).$$ Define a linear transformation $A$ by mapping $\frac{x - y}{\|x - y\|}$ to $\frac{z - y}{\|x - y\|}$ and $e_i$ to $0$ for $i \ge 2$. Note that $$A(x - y) = z - y \implies z = Ax + (I - A)y.$$ I also claim that $A$ and $I - A$ are positive definite. To see this, consider a vector $v = \sum_{i=1}^N a_i e_i$, then $$v \cdot (Av) = \sum_{i = 1}^N \sum_{j = 1}^N a_i a_j e_i \cdot Ae_j = a_1^2 \frac{x - y}{\|x - y\|} \cdot \frac{z - y}{\|x - y\|} \ge 0.$$ Also consider, $$v \cdot ((I - A)v) = \|v\|^2 - v \cdot (Av) = \sum_{i=2}^N a_i^2 + a_1^2 \left[1 - \frac{(x - y) \cdot (z - y)}{\|x - y\|^2}\right] \ge 0$$ as $\|x - y\|^2 - (x - y) \cdot (z - y) = (x - y) \cdot (x - z) \ge 0$. Thus $0 \preceq A \preceq I$ as required.