3
$\begingroup$

For a matrix $\mathbf{X} \in \mathbb{R}^{n\times l}$, we have the following problem of representing vectors in $\mathbf{X}$ as a convex combination of other vectors excluding the vector itself:

$\min\Vert\mathbf{X-XC}\Vert_F^2 \;\; s.t.\;\; diag(\mathbf{C})=0, \;\mathbf{c}_i\geq 0, \;\mathrm{and}\; \Vert\mathbf{c}_i\Vert_1=1$

where $\mathbf{c}_i$, is a column of $\mathbf{C}$, and $diag()$ extracts the diagonal elements of a matrix.

1) Do we have a unique solution or not?

2) What is an efficient way to solve this quadratic program?

$\endgroup$
1
  • $\begingroup$ @RodrigodeAzevedo Duplicate removed. $\endgroup$
    – Astro
    Nov 7, 2016 at 5:46

1 Answer 1

4
$\begingroup$

I guess, uniqueness depends on the rank of $X$.

I would also suggest to look at the reformulate with vectorization as $$\newcommand{\vec}{\operatorname{vec}} \|X-XC\|_F^2 = \|\vec(X) - (I\otimes X)\vec(C)\|_2^2. $$ The constraints are fairly simple to project on (it basically constrains the columns of $C$ to be in the simplex and projecting onto the simplex can be done fast). Depending on the size and further characteristics of the problem you may use a standard QP-solver (noting that the constraints are indeed linear equality and inequality constraints) or simple projected gradient descent.

$\endgroup$
7
  • $\begingroup$ So, do we have a unique solution is $\mathbf{X}$ is full rank? $\endgroup$
    – Astro
    Nov 4, 2016 at 5:14
  • $\begingroup$ Shouldn't the LHS be $\rm \|X-XC\|_F^2$? $\endgroup$ Nov 4, 2016 at 9:39
  • 1
    $\begingroup$ Oops, thanks, @RodrigodeAzevedo. Since $\newcommand{\rank}{\operatorname{rank}}\rank(A\otimes B) = \rank(A)\rank(B)$, full rank $X$ leads to full rank $I\otimes X$ which should give unique solutions. $\endgroup$
    – Dirk
    Nov 4, 2016 at 11:38
  • $\begingroup$ @Dirk What do u mean by 'unique solutions'? Further I guess you missed the first constraint $diag(\mathbf{C})=0$, how to deal with that? Secondly for full rank case and $l>n$, $\mathbf{X}$ is not invertible, thus each signal can choose vectors from different overlapping sub-spaces i.e., multiple solutions/representations not a unique one. Am I missing something here? $\endgroup$
    – Astro
    Nov 5, 2016 at 4:32
  • $\begingroup$ The constraint on the diagonal just reduces the number of variables. I did not consider if X was tall or fat... In any case, if $I\opines X$ has no kernel, there are multiple solutions. $\endgroup$
    – Dirk
    Nov 5, 2016 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.