[Math] n alternative way to represent the $\operatorname{diag}$ function

article-writingcomputational mathematicslinear algebramatricessoft-question

In optimization, it is common to see the so called $\operatorname{diag}$ function

Given a vector $x \in \mathbb{R}^n$, $\operatorname{diag}(x)$ = $n \times n$ diagonal matrix with components of $x$ on the diagonal

For example:

Optimization that involves inverse operation.

Reformulation of BQP to SDP

The reason of using $\operatorname{diag}$ is because it is used in several platforms such as MATLAB, and people generally understands what the function is supposed to do

Is there a more linear algebra, step by step way of converting a
vector $x \in \mathbb{R}^n$ into a diagonal matrix with components on
the diagonal without having a define a function that directly performs
the task ?

i.e. given $x$, we find a series of functions/steps $f_2 \circ f_1 (x)$ which give us the same matrix as $\operatorname{diag}(x)$

Best Answer

There is a closed form.

$\mbox{diag}(x)=I_n\circ (xu)$ where $\circ$ is the Hadamard product, $I_n$ the identity matrix and $u=[1,\cdots,1]$.

Related Solutions

Solve matrix $2$-norm problem with diagonal matrix constraint

Partial answer for how to go about this numerically (since the objective function may not be everywhere differentiable it seems, so I'm not going to do it analytically).

This is an unconstrained convex optimization problem on $\mathbb{R}^n$. Furthermore, the objective $f$ follows the rules of so-called "Disciplined Convex Programming". Hence, convex optimization software such as CVXPY can handle it. Here's a short script in Python:

import cvxpy as cp
import numpy as np

def main():
    n = 10 # Require n > m 
    m = 5

    F = np.random.randn(n, m)
    A = np.random.randn(m, m)

    b = cp.Variable(n)

    objective = cp.Minimize(cp.norm(A - F.T * cp.diag(b) * F))

    prob = cp.Problem(objective, [])

    result = prob.solve(solver='SCS')

    print(b.value)
    print(result)

main()

(Sub)gradient descent approach

The function $f$ is differentiable at any point $b$ where the matrix $A-F^\text{T}\text{diag}(b)F$ has a unique largest singular value. At such a point, let $u$ and $v$ denote the left and right singular vectors (respectively) corresponding to the (unique) largest singular value. The gradient of $f$ at such a point is $$ \nabla{f}(b)=-Fu\otimes{Fv}, $$ where $\otimes$ denotes component-wise multiplication. At points where $f$ is isn't differentiable, you have to be more careful--look up subgradient descent. I'm not sure what kind of convergence guarantees there are for this, but it will be cheaper than CVXPY.

I implemented a simple version in Python, and my main issue was finding step-sizes that led to convergence--I got lots of oscillation.

Obtaining the degree matrix from the adjacency matrix

As with any linear mapping, the function $F:\mathbb R^n \to \mathbb R^{n\times n}$ that sends a vector $\vec v = (v_1,\ldots,v_n)$ to a diagonal matrix with those entries:

$$ F\, \vec v = \begin{pmatrix} v_1 & & 0 \\ & \ddots & \\ 0 & & v_n \end{pmatrix} $$

is uniquely determined by its action on a basis. With a suitable choice of notation we can turn such a definition into a "formula".

Recall the standard ordered basis for $\mathbb R^n$, namely row vectors:

$$ \textbf e_1 = (1,0,\ldots,0), \ldots, \textbf e_n = (0,\ldots,0,1) $$

We can then define our linear mapping as a sum:

$$ F(v_1,\ldots,v_n) = \sum_{k=1}^n v_k \textbf e_k^T \textbf e_k $$

Note that the product of column vector $\textbf e_k^T$ and the row vector $\textbf e_k$ gives a diagonal $n\times n$ matrix with $1$ in the $k$th diagonal position (and zeros elsewhere). Therefore the summation of these terms gives a diagonal matrix supplying exactly the specified diagonal entries.

Best Answer

Related Solutions

Solve matrix $2$-norm problem with diagonal matrix constraint

Obtaining the degree matrix from the adjacency matrix

Related Question