核稀疏表示公式推导

56 阅读 0 评论 37 点赞

我是靠谱客的博主阔达滑板，最近开发中收集的这篇文章主要介绍核稀疏表示公式推导，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本文是对文章kernel sparse representation with local patterns
for face recognition中2.2节公式的推导
在优化求解中,很多人可能都会见过这个公式:

min β 1 2 ∥ X β - y ∥ 22

而根据正则项的不同,l1正则项,l2正则项,可以进行细分:
http://blog.csdn.net/liyuan123zhouhui/article/details/51882926

对于稀疏表示中的稀疏求解:

min β 1 2 ∥ X β - y ∥ 22 + λ ∥ β ∥ 1

左边项是待求解的系数,右边那一项是正则项,是对解的约束,
是对解的稀疏性的约束,至于为什么加这个正则项就会产生稀疏解
可以看看上面的网址

X表示的是字典,bata表示的是稀疏表示系数,lambda是l1正则项的系数

按照2.2节中的公式3: φ(⋅) 是隐式的特征映射,将向量映射到核空间中,我们假设该映射满足以下条件:
φ(x)Tφ(x)=1 when ∥x∥2=1
即,当X的二范数为1时,其核空间的内积也为1
对于最优解,采用坐标下降法进行求解,那么将其他 βi(i=1⋯n,i≠j) 固定,只对 βj 进行求偏导数:

0 = φ (x j) T [\sum i = 1 n β i φ (x i) - φ (y)] + λ sign (β j)

对于正则项的求导,由于是 λ 乘以 βj 的l1范数,也就是所有的 β 绝对值的和,那么求导后就只剩下 λ∣∣βj∣∣ ,对一个数的绝对值进行求导,得到的就是他的符号函数,对公式进行下一步推导:

0 = φ (x j) T φ (x j) β j + φ (x j) T ⎡ ⎣ \sum i = 1, i \neq j n β i φ (x i) - φ (y) ⎤ ⎦ + λ sign (β j)

↓

β j + λ sign (β j) = φ (x j) T ⎡ ⎣ φ (y) - \sum i = 1, i \neq j n β i φ (x i) ⎤ ⎦

↓

(∣ ∣ β j ∣ ∣ + λ) sign (β j) = φ (x j) T ⎡ ⎣ φ (y) - \sum i = 1, i \neq j n β i φ (x i) ⎤ ⎦

左边括号内都大于0:

sign (β j) = sign ⎛ ⎝ φ (x j) T ⎡ ⎣ φ (y) - \sum i = 1, i \neq j n β i φ (x i) ⎤ ⎦ ⎞ ⎠

↓

β j = α - λ sign (α)

α = φ (x j) T ⎡ ⎣ φ (y) - \sum i = 1, i \neq j n β i φ (x i) ⎤ ⎦

↓

β j = sign (α) (| α | - λ) +

还有这样一个约束:

(s) + = {s, s > 0 0, o t h e r w i s e

这个约束是因为

sign(α) 和

sign(βj) 的符号是相等的,因此

|α|−λ 只能够大于等于0
由于

φ(⋅) 是核映射,因此,上面的公式在核空间可以重新写做:

α = K (x j, y) - \sum n i = 1, i \neq j β i K (x j, x i)

有了l1范数,再自己推导l2范数就简单了,直接给出结果:
代价函数:

min 1 2 ∥ X β - y ∥ 22 + λ ∥ β ∥ 22

β j = ⎡ ⎣ K (x j, y) - \sum i = 1, i \neq j n β i K (x j, x i) ⎤ ⎦ / (1 + 2 λ)

elastic net:
代价函数:

min 1 2 ∥ X β - y ∥ 22 + λ ∥ β ∥ 1 + (1 - λ) ∥ β ∥ 22

β j = s i g n ( α ) { | α | - λ } + ( 3 - 2 λ )

其中:

α = φ (x j) T ⎡ ⎣ φ (y) - \sum i = 1, i \neq j n β i φ (x i) ⎤ ⎦

↓

(s) + = {s, s > 0 0, o t h e r w i s e

下面给出matlab代码:


function [beta iter] = KernelCoorDescent ( R, Z, opt )
% Kernel Coordinate Descent (KCD) Algorithm Version 1.0
% KCD is for learning sparse representation in kernel space.
%
% Input:
% R = K(X,X) is a P-by-P kernel matrix, where P is the number of samples.
%
For example, R = X' * X in linear case.X是训练样本？
% Z = K(X,Y) is a P-by-1 kernel vector. For example, Z = X' * Y in linear
%
case.
% opt is a structure containing options for the algorithm.
% opt.lambda is the parameter for the l1 penality.
% opt.tol is the tolerance for convergence.
% opt.iter_num is the maximum number of iterations.
%
% Output:
% beta: the cofficient vector for the sparse representation
%
% Reference:
%
Cuicui Kang, Shengcai Liao, Shiming Xiang, and Chunhong Pan. 
%
"Kernel Sparse Representation With Pixel-level and Region-level 
%
Image Feature Kernels For Face Recognition", Neurocomputing, 
%
Volume 133, Pages141-152, 2014.
%
% Author: Kang Cuicui
% Email : cuicui.kang@ia.ac.cn
% Date : 2013/11/20
if isfield( opt, 'lambda')
lambda
= opt.lambda ;
else
lambda
= 0.01 ;
end
if isfield( opt, 'tol')
tol
= opt.tol ;
else
tol
= 1e-6 ;
end
if isfield( opt, 'iter_num')
iter_num
= opt.iter_num ;
else
iter_num
= 50 ;
end
% initializition
[P, N]= size(R);
beta = zeros( N, 1 );
for iter = 1: iter_num
prebeta = beta;
for j = 1 : P
a = Z(j) - R( j, : )*beta;
a = a + beta(j, :);
if abs( a ) < lambda
beta( j, : ) = 0;
else
beta( j, : ) = sign( a ).*( abs( a ) - lambda );
end
end
%
if mod ( iter, 5) == 0
%
fprintf('CoorDescent Iteration %d of %d n', iter, iter_num);
%
end
if norm(beta-prebeta, 'fro' )/norm(prebeta, 'fro' )
< tol
break;
end
end