# Solving Optimization of Least Squares Term with Quadratic Term with Memory Infeasible Matrix

**URL:** <https://discourse.julialang.org/t/solving-optimization-of-least-squares-term-with-quadratic-term-with-memory-infeasible-matrix/132599>\
**Category:** Optimization (Mathematical)\
**Tags:** linearalgebra, convex-optimization, operator, linearsolve, least-squares\
**Created:** [September 23, 2025, 4:22pm UTC](https://discourse.julialang.org/t/solving-optimization-of-least-squares-term-with-quadratic-term-with-memory-infeasible-matrix/132599 "2025-09-23T16:22:21Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [September 23, 2025, 4:22pm UTC](https://discourse.julialang.org/t/solving-optimization-of-least-squares-term-with-quadratic-term-with-memory-infeasible-matrix/132599/1 "2025-09-23T16:22:21Z")

</div>

I want to solve:

\arg \min\_{\boldsymbol{x}} \frac{\lambda}{2} \boldsymbol{x}^{T} \boldsymbol{E}^{T} \boldsymbol{K} \boldsymbol{E} \boldsymbol{x} + \frac{\rho}{2} {\left\| \boldsymbol{A} \boldsymbol{x} - \boldsymbol{y} \right\|}\_{2}^{2}

Where \rho, \lambda \> 0, \boldsymbol{E} = \left[\boldsymbol{I}\_{n}, \; \boldsymbol{0}\_{n} \right] and \boldsymbol{A} = \operatorname{Diag} \left( \boldsymbol{y} \right) \left[\boldsymbol{K}, \; \boldsymbol{1} \right].  
The matix \boldsymbol{K} is a [Kernel Matrix](https://en.wikipedia.org/wiki/Kernel_method).  
It is SPSD matrix, yet I can’t hold it in memory. I can only calculate elements of it, row / column or apply it on a vector / matrix.

Let \tilde{\boldsymbol{x}} = \boldsymbol{E} \boldsymbol{x} = \left[{x}\_{1}, {x}\_{2}, \ldots, {x}\_{n - 1} \right]^{\top} then \boldsymbol{A} \boldsymbol{x} = \begin{bmatrix} {y}\_{1} \left( \boldsymbol{k}\_{1}^{T} \tilde{\boldsymbol{x}} + {x}\_{n} \right) \\ {y}\_{2} \left( \boldsymbol{k}\_{2}^{T} \tilde{\boldsymbol{x}} + {x}\_{n} \right) \\ \vdots \end{bmatrix} where \boldsymbol{k}\_{i} is the i -th row / column of \boldsymbol{K}.  
This implies {\left\| \boldsymbol{A} \boldsymbol{x} - \boldsymbol{y} \right\|}\_{2}^{2} = \begin{bmatrix} {y}\_{1} \left( \boldsymbol{k}\_{1}^{T} \tilde{\boldsymbol{x}} + {x}\_{n} - 1 \right) \\ {y}\_{2} \left( \boldsymbol{k}\_{2}^{T} \tilde{\boldsymbol{x}} + {x}\_{n} - 1 \right) \\ \vdots \end{bmatrix}.

I wonder if there a relatively efficient way to solve the problem given the special structure of the matrices without having \boldsymbol{K} explicitly.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [September 23, 2025, 11:06pm UTC](https://discourse.julialang.org/t/solving-optimization-of-least-squares-term-with-quadratic-term-with-memory-infeasible-matrix/132599/2 "2025-09-23T23:06:05Z")

</div>

Conjugate gradient or other Krylov least-square methods like [LSQR](https://jso.dev/Krylov.jl/stable/solvers/ls/#LSQR) or [CGLS](https://jso.dev/Krylov.jl/stable/solvers/ls/#CGLS) seem like they could be adapted to this? Iterative methods like this only require matrix–vector multiplications.

---

<div class="post-metadata">

**Author:** ![RoyiAvital](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/royiavital/32/571_2.png) [@RoyiAvital](https://discourse.julialang.org/u/RoyiAvital)\
**Post date:** [September 24, 2025, 2:41pm UTC](https://discourse.julialang.org/t/solving-optimization-of-least-squares-term-with-quadratic-term-with-memory-infeasible-matrix/132599/3 "2025-09-24T14:41:15Z")

</div>

On first glance [`LSQR`](https://jso.dev/Krylov.jl/stable/solvers/ls/#LSQR) looks good as it can solve the problem:

\arg \min\_{\boldsymbol{x}} {\left\| \boldsymbol{A} \boldsymbol{x} - \boldsymbol{b} \right\|}\_{2}^{2} + {\lambda}^{2} {\left\| \boldsymbol{x} \right\|}\_{\boldsymbol{F}}^{2}

Which can fit to my case with setting \boldsymbol{F} = \boldsymbol{E}^{T} \boldsymbol{K} \boldsymbol{E}.

Yet the issue is the algorithm asks for \boldsymbol{N} = \boldsymbol{F}^{-1} which makes it not feasible to my case.

Unless I miss something.

Another issue is the matrices are required to be SPD while \boldsymbol{E}^{T} \boldsymbol{K} \boldsymbol{E} is only SPSD.

### Update

It seems I can control it with `ldiv` as in [`Krylov.jl` - Pre Conditioners](https://jso.dev/Krylov.jl/stable/preconditioners):

 ![image](https://global.discourse-cdn.com/julialang/original/3X/8/e/8e25f1c6477c49f6fa048e5b01dfef6c429918ad.png)