# “Batchwise” least squares with smoothness in row direction as extra objective

My math background is essentially non-existant, so please bear with me.

I have a "batchwise" (for lack of a better term) linear least squares problem $$A X = Y$$ that I solve like $$\hat X = A^\dagger Y$$ with the individual observations and fitted samples as column vectors of $$Y$$ and $$\hat X$$, respectively. Now I would like to add an extra smoothness objective in the row direction of $$\hat X$$ (i.e. a penalty proportional to the derivatives of the $$\hat X^T_i$$ row vectors). I know, that this is no longer a least squares problem. But what is its formal definition? Can it be written as a QP problem and what can be said about convexity? The only sensible approach I can think of is solving it with non-linear optimization which works but is too expensive for the sample sizes I am working with.

When googling, the most promising thing popping up was multi-objective matrix decomposition but the corresponding papers are out of my depth.

Any pointers about how to best approach this would be highly appreciated.

• Are you minimizing $\sum_{i=1}^{k} \| (AX_{i} - Y_{i} \|_{2}^{2} +\lambda \| LX \|_{F}^{2}$ or $\sum_{i=1}^{k} \| AX_{i}-Y_{i} \|_{2} + \lambda \| LX \|_{F}$? The first one is a linear least squares problem in $\mbox{vec}(X)$, while the second is easily expressed as a second order cone programming problem. – Brian Borchers May 3 at 15:01
• @BrianBorchers The first case. I already realized that this can be written in vec(X), but what would be the best way of solving it? I thought about unraveling X and stacking repeats of A but I guess there is a smarter way? – zeawoas May 3 at 22:25
• A lot depends on the size of the problem and the spar site of the matrices. If you use a matrix free iterative method you won’t have to store multiple copies of A. – Brian Borchers May 4 at 3:43
• True, gonna look into a few matrix free implementations. Thanks! – zeawoas May 4 at 9:21
• Do you have any suggestions for suitable software packages / modelling frameworks, preferably (but not necessarily) for python? My current implementation builds A and L as block sparse matrices and then calls scipy.optimize.lsq_linear to solve everything in one go. However, given my matrix sizes (Y: 2500x250, A unstacked: 2500x10, X: 10x250; all of them are dense) this takes too long. I have looked at pylops.readthedocs.io/en/latest/index.html# and cvxpy.org but cannot decide. Any experience with one of these? – zeawoas May 5 at 17:51