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.

  • $\begingroup$ 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. $\endgroup$ – Brian Borchers May 3 at 15:01
  • $\begingroup$ @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? $\endgroup$ – zeawoas May 3 at 22:25
  • $\begingroup$ 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. $\endgroup$ – Brian Borchers May 4 at 3:43
  • $\begingroup$ True, gonna look into a few matrix free implementations. Thanks! $\endgroup$ – zeawoas May 4 at 9:21
  • $\begingroup$ 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? $\endgroup$ – zeawoas May 5 at 17:51

Your Answer

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

Browse other questions tagged or ask your own question.