Amplitude Maximization as a Constrained Monomial Problem

Hello! Welcome to the third lesson in our course.

Introduction

In our previous lesson, we made a crucial conceptual shift. We saw that determining a future value $x_t$ of a difference equation, given its initial values $x_0,\dots ,x_{n-1}$, is equivalent to a polynomial extrapolation problem. We framed this using a linear functional $\mathcal{L}$, defined by the initial values such that $\mathcal{L}(z^k)=x_k$. Finding $x_t$ then became the problem of evaluating $\mathcal{L}(z^t)$.

Today, our goal is to make this connection more concrete and use it to reformulate the paper's central optimization problem. The learning outcome for this lesson is to:

Restate the amplitude maximization problem as a problem of maximizing a linear combination of monomial values, subject to interpolation constraints.

This step is where the problem truly transforms from one of analyzing difference equations to one of optimizing a function in polynomial algebra.

1. The Interpolating Polynomial for the Monomial $z^t$

Let's start with the key players: the characteristic roots ${\lambda }_1,\dots ,{\lambda }_n$ and the time step $t\ge n$. For now, let's assume the roots are distinct.

The core idea is to consider the function $g(z)=z^t$. From the theory of polynomial interpolation, we know there exists a unique polynomial of degree at most $n-1$ that passes through the $n$ points $({\lambda }_i,{\lambda }_i^t)$. Let's call this polynomial ${\psi }_t(z)$.

By definition, ${\psi }_t(z)$ satisfies:
${\psi }_t({\lambda }_i)={\lambda }_i^t\text{for }i=1,\dots ,n$

Since ${\psi }_t(z)$ is a polynomial of degree at most $n-1$, we can write it in the standard monomial basis $\{1,z,z^2,\dots ,z^{n-1}\}$:
${\psi }_t(z)={\sum }_{k=0}^{n-1}{\psi }_{t,k}{z}^k$
The coefficients ${\psi }_{t,k}$ are complex numbers that depend on the time step $t$ and, crucially, on the choice of interpolation nodes—the characteristic roots ${\lambda }_1,\dots ,{\lambda }_n$.

2. Expressing $x_t$ as a Linear Combination

Now, let's connect this new polynomial ${\psi }_t(z)$ to our sequence value $x_t$. We'll use the linear functional $\mathcal{L}$ from the last lesson. Recall its two key properties:

1. It's defined by the initial values: For any polynomial $P(z)=\sum a_k{z}^k$, $\mathcal{L}(P)=\sum a_k\mathcal{L}(z^k)=\sum a_k{x}_k$.
2. It's related to the solution structure: $\mathcal{L}(P)={\sum }_{i=1}^n{c}_{i}P({\lambda }_i)$, where the $c_i$ are the coefficients in the general solution $x_t=\sum c_i{\lambda }_i^t$.

Let's apply the functional $\mathcal{L}$ to our interpolating polynomial ${\psi }_t(z)$. We can evaluate $\mathcal{L}({\psi }_t)$ in two ways:

Method 1: Using the definition of $\mathcal{L}$ via initial values.
Since ${\psi }_t(z)={\sum }_{k=0}^{n-1}{\psi }_{t,k}{z}^k$, we have:
$\mathcal{L}({\psi }_t)={\sum }_{k=0}^{n-1}{\psi }_{t,k}\mathcal{L}(z^k)={\sum }_{k=0}^{n-1}{\psi }_{t,k}{x}_k$
This shows that $\mathcal{L}({\psi }_t)$ is a linear combination of the initial values $x_0,\dots ,x_{n-1}$.

Method 2: Using the structure of the solution.
Using the second property of $\mathcal{L}$ and the defining property of ${\psi }_t(z)$:
$\mathcal{L}({\psi }_t)={\sum }_{i=1}^n{c}_i{\psi }_t({\lambda }_i)={\sum }_{i=1}^n{c}_i{\lambda }_i^t$
This sum is, by definition, the value of the solution at time $t$, which is $x_t$.

By equating the results of both methods, we arrive at a remarkable formula:
$x_t={\sum }_{k=0}^{n-1}{\psi }_{t,k}{x}_k$

This equation is the heart of today's lesson. It states that any future value $x_t$ is a specific linear combination of the initial values. The weights of this combination, ${\psi }_{t,k}$, are precisely the coefficients of the polynomial that interpolates the monomial $z^t$ at the characteristic roots of the system.

3. The Paper's Formulation

This reduction is a key step in the paper's argument. Let's see how the authors present it.

As you saw, the paper's "Fact 2.1" is exactly what we derived. It states that for $t\ge n$, the solution $x_t$ is given by ${\psi }_t^T{x}_{0:n-1}$, where ${\psi }_t$ is the vector of coefficients for the polynomial of degree $n-1$ that interpolates $z^t$ on the roots $z_{1:n}$.

4. Restating the Maximization Problem

Now we can finally restate the original problem. We want to maximize $|x_t|$ over all valid choices of characteristic roots and initial values.

The original problem:
${\max }_{\begin{array}{c}|{\lambda }_i|\le r\\ |x_k|\le 1\end{array}}|x_t|$

Using our new expression for $x_t$:
${\max }_{\begin{array}{c}|{\lambda }_i|\le r\\ |x_k|\le 1\end{array}}\left|{\sum }_{k=0}^{n-1}{\psi }_{t,k}({\lambda }_1,\dots ,{\lambda }_n)x_k\right|$

Let's analyze the inner maximization over the initial values $x_k$, assuming the roots ${\lambda }_i$ (and therefore the coefficients ${\psi }_{t,k}$) are fixed. We want to maximize the magnitude of a sum of complex numbers, ${\sum }_{k=0}^{n-1}{\psi }_{t,k}{x}_k$, where the $x_k$ can be any complex number in the unit disk.

By the triangle inequality, we have:
$\left|{\sum }_{k=0}^{n-1}{\psi }_{t,k}{x}_k\right|\le {\sum }_{k=0}^{n-1}|{\psi }_{t,k}||x_k|$
Since $|x_k|\le 1$, this is further bounded by ${\sum }_{k=0}^{n-1}|{\psi }_{t,k}|$. This upper bound is achieved by choosing each $x_k$ to have modulus 1 and a phase that perfectly cancels the phase of the corresponding ${\psi }_{t,k}$. Specifically, if ${\psi }_{t,k}=|{\psi }_{t,k}|e^{i{\varphi }_k}$, we choose $x_k=e^{-i{\varphi }_k}$.

Therefore, for a fixed set of roots, the maximization over initial values yields:
${\max }_{|x_k|\le 1}\left|{\sum }_{k=0}^{n-1}{\psi }_{t,k}{x}_k\right|={\sum }_{k=0}^{n-1}|{\psi }_{t,k}|$
This is the ${\ell }_1$-norm of the vector of coefficients of the interpolating polynomial ${\psi }_t(z)$.

Our full optimization problem is now reduced to maximizing this ${\ell }_1$-norm over the choice of roots:
${\max }_{|{\lambda }_1|\le r,\dots ,|{\lambda }_n|\le r}\left({\sum }_{k=0}^{n-1}|{\psi }_{t,k}({\lambda }_1,\dots ,{\lambda }_n)|\right)$

This is the reformulated problem. Let's break down how it matches the learning outcome:

• "Maximizing a linear combination of monomial values": The quantity we are maximizing, $|x_t|$, is $|\mathcal{L}(z^t)|$, the magnitude of our functional applied to the monomial $z^t$. We have shown this is equivalent to maximizing the ${\ell }_1$-norm of the coefficients ${\psi }_{t,k}$.
• "Subject to interpolation constraints": The coefficients ${\psi }_{t,k}$ are not free variables. They are implicitly defined by the interpolation problem: they are the coefficients of the unique polynomial ${\psi }_t(z)$ of degree $\le n-1$ that interpolates $z^t$ at the roots ${\lambda }_i$. The optimization is over the choice of these interpolation nodes.

Conclusion

In this lesson, we have successfully translated the problem of amplitude maximization into the language of polynomial interpolation. This is a significant step, moving us from the domain of linear algebra and difference equations into complex analysis and algebra, where different and more powerful tools are available.

Key Takeaways:

• The value of a difference equation solution at time $t$, $x_t$, can be expressed as a linear combination of the initial values: $x_t={\sum }_{k=0}^{n-1}{\psi }_{t,k}{x}_k$.
• The coefficients ${\psi }_{t,k}$ are the coefficients of the unique polynomial of degree $\le n-1$ that interpolates the function $g(z)=z^t$ at the system's characteristic roots.
• Maximizing $|x_t|$ over all allowed initial values (for fixed roots) is equivalent to computing the ${\ell }_1$-norm of the coefficient vector ${\psi }_t$.
• The overall problem is now to choose the characteristic roots ${\lambda }_i$ within the disk of radius $r$ to maximize this ${\ell }_1$-norm.

The problem is now to find the configuration of $n$ points in a disk that makes the ${\ell }_1$-norm of the coefficients of this specific interpolating polynomial as large as possible. This is a non-trivial problem in approximation theory.

Preview of the Next Lesson:

To solve this new problem, we need to understand how the coefficients ${\psi }_{t,k}$ depend on the roots ${\lambda }_i$. This dependency is quite complex, but it has a beautiful underlying structure related to symmetric polynomials. In the next lesson, we will introduce the algebraic toolkit needed to analyze this structure, starting with elementary symmetric polynomials and their relationship to the coefficients of the characteristic polynomial.