How to solve a regularized least square problem in Matlab?
pradeepa
I want to solve a minimization problem in the manner below.
min (||delta * A|| + lamda||A - A'||)
where delta is the laplacian operator or a derivative operator, lamda is the regularization parameter, ||.|| represent the Frobenius norm and A and A' are matrices. Could any of you help me to solve this in Matlab?
Thanks ,
Dev
Bruno Luong
Posed like that, the problem seem odd mathematically. The Frobenius's norm ||A|| is too "weak" to regularize ||delta A||, because there is no inclusion of two correspondent Banach spaces.
If you accept to minimize the sum of the *square* of the norms rather than the sum of the norms, then the problem is linear. Just write down the function and take the gradient of it. It gives the linear system.
Though your system is still singular, because adding any function with delta*A = 0 (solution of Poisson equation with appropriate boundary) will give the same cost function.
If you minimize the sum of the norm than the cost function has the square-root. You migh use FMINUNC to minimize the function (convex). The ill-posedness of your problem is still there though.
Bruno
pradeepa
Thanks for the reply. I was referring to a paper and there seems to some error in the formula. The correct formula is
min (||delta * A||^2 + lamda||M .(A - A')||^2)
where delta is the laplacian operator, * is the convolution operator,lamda is the regularization parameter, ||.|| represent the Frobenius norm , . is for matrix multiplication, M is a mask operator (a matrix which can be regarded as an identity matrix) and A and A' are matrices.
I tried solving in the fourier domain but got stuck with the combination of Mask operator with A.
Any help is greatly appreciated.
"Bruno Luong" <b.l...@fogale.findmycountry> wrote in message <h6avbn$h7k$1...@fred.mathworks.com>...
Bruno Luong
>
> I tried solving in the fourier domain but got stuck with the combination of Mask operator with A.
Why can you just write down the discrete operator of the above in term of matrix, then solve it using backslash. It is a straight-forward linear problem.
Bruno
pradeepa
Hi,
I didn't quite understand what you meant by backslash. Would you mind explaining a little bit more?
I actually tested by taking the convolution as a block toeplitz matrix and minimizing as a least square function using lsqlin function.
When I convert delta
to a block Toeplitz format in order to convert the convolution to
a matrix multiplication, the matrix become very large and I turned
all the resulting matrices to sparse format. The lsqlin method resulted in out of memory problem.
Is there any other way to handle this which I am not aware of?
Any help is greatly appreciated.
Thanks
resulted in
Bruno Luong
> "Bruno Luong" <b.l...@fogale.findmycountry> wrote in message <h6g8gd$a8e$1...@fred.mathworks.com>...
>
> I didn't quite understand what you meant by backslash. Would you mind explaining a little bit more?
Backslash "\" is Matlab matrix division/inversion operator. Hep MLDIVIDE.
>
> I actually tested by taking the convolution as a block toeplitz matrix and minimizing as a least square function using lsqlin function.
> When I convert delta
> to a block Toeplitz format in order to convert the convolution to
> a matrix multiplication, the matrix become very large and I turned
> all the resulting matrices to sparse format. The lsqlin method resulted in out of memory problem.
>
> Is there any other way to handle this which I am not aware of?
I'm not sure what is your operator. If it's a discrete laplacian operator, the sparse matrix should not cost too much in term of memory. Poisson operators are used in many areas.
If it's a full convolution, use CONV command instead of explicitly build your matrix (similarly nobody build FFT matrix).
Bruno