Skip to main content
added 298 characters in body
Source Link

Context:

I'm working on a convergence theorem for an accelerated version of an iterative optimisation algorithm. At regularly-spaced intervals during the algorithm, a number of previous (unaccelerated) iterates are linearly combined to form a new (accelerated) iterate.

I need to know if the map the combines the iterates is a ($C^1$-)diffeomorphism.

Details:

The unaccelerated algorithm produces a sequence $x_0,\dots, x_k, x_{k+1}$ of linearly independent vectors in $\mathbb{R}^n$.

The map $R$ takes the most recent iterate $x = x_{k+1}$ to the new iterate $R(x)$: $$R : \mathbb{R}^{n} \to \mathbb{R}^n, \quad x \mapsto R(x) = \sum_{j=0}^k c_j x_j.$$ The coefficients $c_j$ depend on $x$, and are the solution to an equality-constrained optimisation problem. I have a closed-form expression for $c$: $$c = \frac{(U^{\top}U)^{-1}\mathbf{1}}{\mathbf{1}^{\top}(U^{\top}U)^{-1}\mathbf{1}},$$ where $\mathbf{1} \in \mathbb{R}^{k+1}$ is a column vector of ones, and where the matrix $U \in \mathbb{R}^{n\times(k+1)}$ has rank $k+1$, and is defined by $$U = [x_1 - x_0, x_2 - x_1, \dots, x - x_k].$$ (The important term is the $x$ in the rightmost column.)

Is the map $R$ a diffeomorphism?

Or is there a manifold on which it is?

Clearly $R$ is injective and differentiable. Is it invertible at each $x\in \mathbb{R}^n$ such that the aforementioned linear-independence/full-rank conditions hold? Is the inverse (once-)differentiable at these points?

EDIT:

I'm assuming that $x_{k+1}$ is such that $U$ has rank $k+1$ for all $x$ in an open neighbourhood of $x_{k+1}$. If this were not the case, my algorithm would skip the application of $R$. So the revised question becomes, is $R$ a diffeomorphism when restricted to that neighbourhood?

Context:

I'm working on a convergence theorem for an accelerated version of an iterative optimisation algorithm. At regularly-spaced intervals during the algorithm, a number of previous (unaccelerated) iterates are linearly combined to form a new (accelerated) iterate.

I need to know if the map the combines the iterates is a ($C^1$-)diffeomorphism.

Details:

The unaccelerated algorithm produces a sequence $x_0,\dots, x_k, x_{k+1}$ of linearly independent vectors in $\mathbb{R}^n$.

The map $R$ takes the most recent iterate $x = x_{k+1}$ to the new iterate $R(x)$: $$R : \mathbb{R}^{n} \to \mathbb{R}^n, \quad x \mapsto R(x) = \sum_{j=0}^k c_j x_j.$$ The coefficients $c_j$ depend on $x$, and are the solution to an equality-constrained optimisation problem. I have a closed-form expression for $c$: $$c = \frac{(U^{\top}U)^{-1}\mathbf{1}}{\mathbf{1}^{\top}(U^{\top}U)^{-1}\mathbf{1}},$$ where $\mathbf{1} \in \mathbb{R}^{k+1}$ is a column vector of ones, and where the matrix $U \in \mathbb{R}^{n\times(k+1)}$ has rank $k+1$, and is defined by $$U = [x_1 - x_0, x_2 - x_1, \dots, x - x_k].$$ (The important term is the $x$ in the rightmost column.)

Is the map $R$ a diffeomorphism?

Or is there a manifold on which it is?

Clearly $R$ is injective and differentiable. Is it invertible at each $x\in \mathbb{R}^n$ such that the aforementioned linear-independence/full-rank conditions hold? Is the inverse (once-)differentiable at these points?

Context:

I'm working on a convergence theorem for an accelerated version of an iterative optimisation algorithm. At regularly-spaced intervals during the algorithm, a number of previous (unaccelerated) iterates are linearly combined to form a new (accelerated) iterate.

I need to know if the map the combines the iterates is a ($C^1$-)diffeomorphism.

Details:

The unaccelerated algorithm produces a sequence $x_0,\dots, x_k, x_{k+1}$ of linearly independent vectors in $\mathbb{R}^n$.

The map $R$ takes the most recent iterate $x = x_{k+1}$ to the new iterate $R(x)$: $$R : \mathbb{R}^{n} \to \mathbb{R}^n, \quad x \mapsto R(x) = \sum_{j=0}^k c_j x_j.$$ The coefficients $c_j$ depend on $x$, and are the solution to an equality-constrained optimisation problem. I have a closed-form expression for $c$: $$c = \frac{(U^{\top}U)^{-1}\mathbf{1}}{\mathbf{1}^{\top}(U^{\top}U)^{-1}\mathbf{1}},$$ where $\mathbf{1} \in \mathbb{R}^{k+1}$ is a column vector of ones, and where the matrix $U \in \mathbb{R}^{n\times(k+1)}$ has rank $k+1$, and is defined by $$U = [x_1 - x_0, x_2 - x_1, \dots, x - x_k].$$ (The important term is the $x$ in the rightmost column.)

Is the map $R$ a diffeomorphism?

Or is there a manifold on which it is?

Clearly $R$ is injective and differentiable. Is it invertible at each $x\in \mathbb{R}^n$ such that the aforementioned linear-independence/full-rank conditions hold? Is the inverse (once-)differentiable at these points?

EDIT:

I'm assuming that $x_{k+1}$ is such that $U$ has rank $k+1$ for all $x$ in an open neighbourhood of $x_{k+1}$. If this were not the case, my algorithm would skip the application of $R$. So the revised question becomes, is $R$ a diffeomorphism when restricted to that neighbourhood?

Source Link

Is the following map a diffeomorphism?

Context:

I'm working on a convergence theorem for an accelerated version of an iterative optimisation algorithm. At regularly-spaced intervals during the algorithm, a number of previous (unaccelerated) iterates are linearly combined to form a new (accelerated) iterate.

I need to know if the map the combines the iterates is a ($C^1$-)diffeomorphism.

Details:

The unaccelerated algorithm produces a sequence $x_0,\dots, x_k, x_{k+1}$ of linearly independent vectors in $\mathbb{R}^n$.

The map $R$ takes the most recent iterate $x = x_{k+1}$ to the new iterate $R(x)$: $$R : \mathbb{R}^{n} \to \mathbb{R}^n, \quad x \mapsto R(x) = \sum_{j=0}^k c_j x_j.$$ The coefficients $c_j$ depend on $x$, and are the solution to an equality-constrained optimisation problem. I have a closed-form expression for $c$: $$c = \frac{(U^{\top}U)^{-1}\mathbf{1}}{\mathbf{1}^{\top}(U^{\top}U)^{-1}\mathbf{1}},$$ where $\mathbf{1} \in \mathbb{R}^{k+1}$ is a column vector of ones, and where the matrix $U \in \mathbb{R}^{n\times(k+1)}$ has rank $k+1$, and is defined by $$U = [x_1 - x_0, x_2 - x_1, \dots, x - x_k].$$ (The important term is the $x$ in the rightmost column.)

Is the map $R$ a diffeomorphism?

Or is there a manifold on which it is?

Clearly $R$ is injective and differentiable. Is it invertible at each $x\in \mathbb{R}^n$ such that the aforementioned linear-independence/full-rank conditions hold? Is the inverse (once-)differentiable at these points?