Frobenius norm with Kronecker product for rank-1 solution

Question

Let $ Y \in \mathbb{C}^{L \times N} $. I need to find the vector $ x $.

\begin{equation*} \min_{x}\left\|Y-(1^T\otimes x)\right\|_F^2. \end{equation*}

My problem is on decoupling $ x $ from the Kronecker operator. Any hints?

Answer 1

So $1 \otimes x$ is a matrix which contains the vector $x$ in every column. Denoting the $j$'th column of $Y$ by $Y_{:j}$, we thus have $$L(x) := \lVert Y - 1 \otimes x \rVert_F^2 = \sum_{j=1}^N \lVert Y_{:j} - x\rVert_2^2. $$ Taking the derivative with respect to $x$ gives $$ \nabla_x L(x) = -2 \sum_{j=1}^N (Y_{:j} - x) = -2 \sum_{j=1}^N (Y_{:j}) + 2Nx. $$ Setting this to zero yields $$ x = \frac{1}{N} \sum_{j=1}^N Y_{:j}. $$

Answer 2

You can replace the Kronecker product with the outer product of vectors and write $$\eqalign{ \def\o{{\tt1}}\def\R{{\mathbb R}} \min_x\,\left\|Y-x\o^T\right\|^2_F \qquad x\in\R^L\quad \o\in\R^N }$$ However, this is simply the least squares solution of a linear equation $$\eqalign{ x\o^T &= Y \\ }$$ whose closed-form solution can be written using the pseudoinverse $$\eqalign{ x &= Y\,\Big(\o^T\Big)^+ \;=\; Y\left(\frac{\o}{\o^T\o}\right) \;=\; \frac{Y\o}{N} \\ }$$ Derivatives are not needed.

Answer 3

Denote $\mathbf{y}_n$ the $n$-th column of $\mathbf{y}$.

The cost function to be minimized can also be written $$ \phi(\mathbf{x}) = \sum_n \delta_E^2(\mathbf{x},\mathbf{y}_n) $$ This is similar to compute a Karcher mean wiki using Euclidean distance. The minimum is reached at the arithmetic mean of the $N$ vectors $\{\mathbf{y}_n\}$.