0

I have an expression for a scalar, which is the double sum over vector-matrix-vector products. All terms are real-values vectors/matrices and dimensions are below each term:

$$\sum_{i=1}^N \sum_{j=1}^N \underbrace{a_i^T}_{1 \times k} \underbrace{B_i}_{k \times k} \underbrace{K_i}_{k \times p} \underbrace{K_j^T}_{p \times k} \underbrace{B_j^T}_{k \times k} \underbrace{a_j}_{k \times 1} $$

I'd like to simplify this expression such that the double sums are absorbed and I have a single vector-matrix-vector product, maybe something like:

$$\underbrace{x^T}_{1 \times kN} \quad \underbrace{P}_{kN \times kN} \quad \underbrace{x}_{kN \times 1}$$

where $P$ depends on the $B_i, K_i$ matrices and $x$ depends on the $a_i$ vectors.

But I don't know how to collapse $B_i, K_i$ to form $P$. Can someone please help me? I think the Kronecker product might be useful, but I'm not sure and I'm not too familiar with it.

If this question has already been asked/answered, please point me towards that!

Edit: Made clear that $P$ should depend only on $B_i, K_i$ and $x$ should depend only on $a_i$s. I need this because I want to understand how $B_i, K_i$ together determine the eigenspectrum of $P$.

Edit 2: All I want is $\begin{bmatrix}a_1\\ \vdots\\ a_N\end{bmatrix}^T \begin{bmatrix} B_1 K_1 K_1^T B_1^T & \dots & B_1 K_1 K_N^T B_N^T\\ \vdots & \ddots & \\ B_N K_N K_1^T B_1^T & & B_N K_N K_N^T B_N^T \end{bmatrix} \begin{bmatrix}a_1\\ \vdots\\ a_N\end{bmatrix}$. Is there no way to express this using a Kronecker product or some other operation?

Rylan Schaeffer
  • 462

1 Answers1

1

I'll contract implicitly over repeated indices. Using upper case indices to denote components, your expression is $a_{iA}B_{iAB}K_{iBC}K_{jDC}B_{jED}a_{jE}$ (or perhaps more helpfully $a_{iA}B_{iAB}K_{iBC}a_{jE}B_{jED}K_{jDC}$), since e.g. $(K_j^T)_{CD}=K_{jDC}$. Note each upper case index assumes one of $k$ possible values. This is an expression of the form $x_{iC}x_{jC}$ with $x_{iC}:=a_{iA}B_{iAB}K_{iBC}=(K^T_iB^T_ia_i)_C$. If we treat a one-lower-one-upper letter pair as an index on a $kN$-dimensional space, this is just a dot product $x^Tx$ (modulo a subtlety), so $P$ is an identity matrix.

Edit to address a clarification: or you could take $a_{iA}^TP_{iAjE}a_{jE}$ with $P_{iAjE}=B_{iAB}K_{iBC}K_{jDC}B_{jED}$.

J.G.
  • 115,835
  • Nothing here is wrong, but I see now that I left out a crucial detail. I want to be able to analyze the spectrum of $P$ (and therefore when I wrote $x^T P x$, I meant that $x$ depend only on the $a_i$s. – Rylan Schaeffer Aug 04 '20 at 19:06
  • @RylanSchaeffer I've edited in such a treatment where $x_{iA}=a_{iA}$. – J.G. Aug 04 '20 at 19:08
  • Ok thank you! I guess what I'm struggling with is how $P$ written in einsum notation can help me understand its spectrum. Mechanically, I understand how to form $P$, but how does that tell me its spectrum? – Rylan Schaeffer Aug 04 '20 at 19:11
  • @RylanSchaeffer You'd have to solve $B_{iAB}K_{iBC}K_{jDC}B_{jED}V_{jE}=\lambda V_{iA}$, which can't be done with any theorem I know, because there are four indices of two different kinds at work here, mixing in quite a complicated way. – J.G. Aug 04 '20 at 19:16
  • I guess I'm pretty stumped. I was trying to abstract away unnecessarily details, but an almost identical problem is exactly what's addressed in the Neural Tangent Kernel literature and they seem to be able to compute the eigenspectra just fine. The only difference between my question and their work is that now there's a metric B_i – Rylan Schaeffer Aug 04 '20 at 19:40
  • All I want is $\begin{bmatrix}a_1\ \vdots\ a_N\end{bmatrix}^T \begin{bmatrix} B_1 K_1 K_1^T B_1^T & \dots & B_1 K_1 K_N^T B_N^T\ \vdots & \ddots & \ B_N K_N K_1^T B_1^T & & B_N K_N K_N^T B_N^T \end{bmatrix} \begin{bmatrix}a_1\ \vdots\ a_N\end{bmatrix}$. Is there no way to express this using a Kronecker product or some other matrix operation? – Rylan Schaeffer Aug 05 '20 at 15:33