# How to solve linear equations with structured matrices?

Suppose $$\mathbf{x}\in R^{m\times 1}$$, $$\mathbf{X} = [\mathbf{x}\, \mathbf{x}\, \cdots]^\top\in R^{nm\times 1}$$ and $$\mathbf{b}\in R^{nm\times 1}$$ and $$\mathbf{A}\in R^{nm\times nm}$$. How to solve

$$$$\mathrm{argmin}_{\mathbf{x}} (\mathbf{b}-\mathbf{A}\mathbf{X})^\top(\mathbf{b}-\mathbf{A}\mathbf{X})$$$$ ?

Notice that argmin is w.r.t. the small $$\mathbf{x}$$.

(actually, what is the derivative of that objective function w.r.t. $$\mathbf{x}$$?)

• Kronecker products and vectorizations – mathreadler Nov 18 '19 at 20:39

Hint. Consider the bilinear form $$\psi(x,y)=(x|y)$$ (inner product). Then, $$\psi'(x,y)\cdot (h,k)=\psi(x,k)+\psi(h,y).$$ Also, the function $$x\mapsto X=(x,\ldots,x)$$ is linear, thus its derivative at any point is itself. Similarly, define $$u(y)=(y,y),$$ which is also linear and $$v(t)=b-At,$$ which has derivative $$v'(t) \cdot s=As.$$ You want to differentiate $$\psi \circ u \circ v \circ X,$$ which follows readily from chain rule.