I need to find $g$ that minimizes: $$\sum_{v=0}^n (f+g_{v_{left}}-g_{v_{right}})^2 + \frac{1}{\lambda}\sum_{v=0}^m (g_{v_i}-g_{v_j})^2$$ where $f$ is constant and the sums are over pair of $v$ indices; such that: $$\left\lVert g \right\rVert$$ is also minimized. Both $f$ and $g$ are vectors.
I can solve the first equation alone by converting it to matrix form: $$\left\lVert Ag-f \right\rVert^2+\left\lVert Γg \right\rVert^2 = g^T(A^TA+Γ^TΓ)g-2f^tAg+f^Tf$$ where $A$ and $Γ$ (Tikhonov's Gamma matrix) are sparse matrices containing ±1 entries to pick the correct $g_{v_{left}}$, $g_{v_{right}}$, $g_{v_i}$ and $g_{v_j}$. This equation is a quadratic form in $g$, and $A^TA+Γ^TΓ$ is very sparse, symmetric and positive semidefinite. I can minimize it with respect to $g$ with Eigen’s conjugate gradient (CG) implementation.
Since the system is under-constrained and I need the solution with minimal $g$, for now I subtract the mean: $g=g-mean(g)$. But this is not enough.
How can I solve the same equation such that the solution $g$ has minimum norm as well?