0
$\begingroup$

Let $\mathbf{A} \in \mathbb{R}^{N \times N}$, $\mathbf{X} \in \mathbb{R}^{N \times M}$, and $\mathbf{B} \in \mathbb{R}^{M \times N}$. We intend to solve for $\mathbf{X}$ by solving the following optimization problem

\begin{align} \arg \min_{\mathbf{X}} || \mathbf{A} - \mathbf{X} \mathbf{B} ||_\mathrm{F} \end{align}

where $||\cdot||_\mathrm{F}$ is the Frobenius norm operator. The above problem can be rewritten as

\begin{align} \arg \min_{\mathrm{vec}(\mathbf{X})} \mathrm{vec}(\mathbf{X})^T (\mathbf{B}\mathbf{B}^T \otimes \mathbf{I}) \mathrm{vec}(\mathbf{X}) - 2 \mathrm{vec}(\mathbf{A} \mathbf{B}^T)^T \mathrm{vec}(\mathbf{X}). \end{align}

where $\otimes$ is the Kronecker product. The above optimization can be solved easily as it is a quadratic program with no constraints. Suppose, we are given prior information that $\mathbf{X}$ is a lower-triangular matrix, how do I impose it as an equality constraint in the form of $\mathbf{C} \mathrm{vec}(\mathbf{X}) = \mathrm{vec}(\mathbf{Y})$ where $\mathbf{C} \in \mathbb{R}^{MN \times MN}$ and $\mathrm{vec}(\mathbf{Y})$ is the vectorized lower-triangular entries of $\mathbf{X}$? In other words, how to determine the entries of matrix $\mathbf{C}$?

Note that I can use cvx in MATLAB to solve this but when the dimensions of the matrices are large, then cvx takes a lot of time for computing.

$\endgroup$
  • 5
    $\begingroup$ Indeed, CVX is not the right tool for this problem. This is actually just a least-squares problem, really. The right thing to do is not to impose an equality constraint to enforce the lower-triangular nature of it. Effectively, what you want to do is just eliminate the rows of the "vectorized" least-squares problem that correspond to the upper triangle of X. $\endgroup$ – Michael Grant Aug 8 '18 at 18:01
  • $\begingroup$ How do I do that? Is $\mathbf{C}$ a diagonal matrix with ones on all those positions which represents the lower-triangular matrix indices? Then, $\mathbf{C}$ may not be full rank. $\endgroup$ – Maxtron Aug 8 '18 at 18:23
  • $\begingroup$ Another bottle neck with this approach is the storage of large Kronecker product. Do you have some useful tricks that might help me overcome this? $\endgroup$ – Maxtron Aug 8 '18 at 18:43
  • 2
    $\begingroup$ Maybe I'm missing something, but why won't @MichaelGrant 's response work? You really have several least squares problems on your hands with objectives of the form $$||a^T_k[1:k] - x_k^TB||$$ where $a_k^T[1:k]\in\mathbf{R}^{k}$ is the first $k$ components of row $k$ in $A$, $x^T_k\in\mathbf{R}^{k}$ is the $k$th row of $X$ $\endgroup$ – Casey Aug 8 '18 at 19:48
  • 1
    $\begingroup$ See page 233: web.stanford.edu/~boyd/vmls/vmls.pdf $\endgroup$ – Casey Aug 8 '18 at 20:28
1
$\begingroup$

The problem is given by:

$$ \arg \min_{X \in \mathcal{T} } \frac{1}{2} {\left\| X B - A \right\|}_{F}^{2} $$

Where $ \mathcal{T} $ is the set of Lower Triangular Matrices.

The set $ \mathcal{T} $ is a Convex Set.
Moreover, the orthogonal projection onto the set of a given matrix $ Y \in \mathbb{R}^{m \times n} $ is easy:

$$ X = \operatorname{Proj}_{\mathcal{T}} \left( Y \right) = \operatorname{tril} \left( Y \right) $$

Namely, zeroing all elements above the main diagonal of $ Y $.

By utilizing the Projected Gradient Descent it is easy to solve this problem:

$$ \begin{align*} {X}^{k + 1} & = {X}^{k} - \alpha \left( X B {B}^{T} - A {B}^{T} \right) \\ {X}^{k + 2} & = \operatorname{Proj}_{\mathcal{T}} \left( {X}^{k + 1} \right)\\ \end{align*} $$

enter image description here

The full MATLAB code with CVX validation is available in my StackExchnage Mathematics Q2876283 GitHub Repository.

The solution is very similar to the solution in Q2421545 - Solve Least Squares (Frobenius Norm) Problem with Diagonal Matrix Constraint.

Remark
I think you can also get a closed form solution for each element in $ X $ if you go through deriving the derivative with respect to each element $ X $.
Another approach would be developing the Linear Operator which operates on $ \frac{ \left( n - 1 \right) n }{2} $ elements and creates an $ n \times n $ Triangular Matrix.

$\endgroup$
  • $\begingroup$ Can a lower-triangular matrix constraint be imposed by $\ell_0$ norm operator? Then, maybe we can accelerate this approach. However, $\ell_0$ norm only constraints that $K$ atoms are non-zero, but does not specify which positions of those $K$ atoms are zeros. $\endgroup$ – Maxtron Aug 13 '18 at 2:14
  • $\begingroup$ @Maxtron, Much easier approach would be imposing zeros on the elements which are not in the lower triangle. It is a linear constraint and target the objective directly hence easier to do (Also keeps the problem Convex). You can either do that by the projection above or use an operator as I wrote in my remark. $\endgroup$ – Royi Aug 13 '18 at 5:30
  • $\begingroup$ The problem with the current approach is that it takes a lot of time to converge when you are dealing with large matrices. Is there a way we can accelerate projected gradient descent? Note that both the cost function and constraints are convex. Perhaps, algorithm like FISTA can be used? $\endgroup$ – Maxtron Aug 13 '18 at 16:21
  • $\begingroup$ @Maxtron, In any problem which is convex and the iteration is Gradient Descent / Proximal Gradient Descent (Generalization of the Projected Gradient Descent) you may use acceleration method such as FISTA. Pay attention that $ B {B}^{T} $ and $ A {B}^{T} $ should be pre calculated. $\endgroup$ – Royi Aug 13 '18 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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