# Solve Matrix Least Squares (Frobenius Norm) Problem with Lower Triangular Matrix Constraint

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.

• 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. – Michael Grant Aug 8 '18 at 18:01
• 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. – Maxtron Aug 8 '18 at 18:23
• 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? – Maxtron Aug 8 '18 at 18:43
• 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$ – Casey Aug 8 '18 at 19:48
• See page 233: web.stanford.edu/~boyd/vmls/vmls.pdf – Casey Aug 8 '18 at 20:28

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*}

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.

• 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. – Maxtron Aug 13 '18 at 2:14
• @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. – Royi Aug 13 '18 at 5:30
• 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? – Maxtron Aug 13 '18 at 16:21
• @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. – Royi Aug 13 '18 at 18:10
• @Maxtron, You may have a look how I used FISTA like acceleration in Projected Gradient Descent (As above) in my answer to How to Solve Linear Least Squares Problem with Box Constraints. – Royi Feb 25 '20 at 7:38