I need to solve a constrained least-squares (LS) problem as follows
$min_X \text{ } ||Y-AX||_F^2$
$s.t. \text{ } {X\in \chi}$
where $A\in R^{n\times m}$, $(n\ge m)$ , $X\in R^{m\times k}$ and $\chi$ denotes the feasible set of solution. Indeed, the solution to the above LS problem must have a predefined sparsity pattern which is represented by the index set $\Omega$. This index set contains the indices of all the non-zero entries in $X$: that is $X_{i,j}\ne 0$ for all $(i,j)\in \Omega$ and $X_{i,j}= 0$ for all $(i,j)\notin \Omega$. Thus the feasible set $\chi$ is defined as
$\chi= $ {$X\in R^{n\times m} : X_{i,j}=0 \text{ } \forall (i,j)\notin\Omega $}
To solve this problem, I first compute the solution of unconstrained LS problem as $X^*=(A^TA)^{-1}A^TY$ and then project it onto the feasible set by setting to zero the elements of $X^*$ that their index does not belong to index set $\Omega$.
I’m not sure about the optimality of the solution obtained by this method. If this method does not lead to correct or optimal solution, how can I solve the above constrained LS problem in an appropriate way? Thanks in advance.
Guess what: this is actually a standard least squares problem in disguise. The key is recognizing the Kronecker structure: $$\|Y-AX\|_F = \|\mathop{\textrm{vec}}(Y)-(I_{k\times k}\otimes A)\mathop{\textrm{vec}}(X)\|_2$$ where $\mathop{\textrm{vet}}:\mathbb{R}^{n\times k}\rightarrow\mathbb{R}^{nk}$ converts a matrix to a vector by stacking its columns on top of one another; and $\otimes$ denotes the Kronecker product.
Once you have that, then really all you want to do is select the columns of $I\otimes A$ that correspond to the nonzero elements of $X$. In particular, if $(i,j)\in\Omega$, then column $(j-1)m+i$ of the matrix $I\times A$ will be present in this new matrix. If there are $p$ elements in $\Omega$, then this new matrix will be of size $nk\times p$. This matrix will actually be quite sparse: each column will have a single column of $A$ in it, inserted at different positions in the length $nk$ vector.
So now you have a least-squares problem with a coefficient matrix of is $nk\times|\Omega|$. Solve that, and you'll have a vector of the non-zero elements of $X$. Fill them in, in columnwise order, and you're done.