精华内容
下载资源
问答
  • 1、matlab代码,实现稀疏表示中L1范数最小化的求解问题。 2、稍微修改了一下函数的接口,解决了用C++调用这个matlab函数时参数传参问题。因为该函数用到了varargin,可变参数传参,而C++参数传递都是固定的。 3、...
  • l1范数最小化求解系数方程:正交匹配追踪法(orthogonal matching pursuit) 本文部分参考[0] 贪婪算法 正交匹配追踪法是信号处理中拟合稀疏模型的一种贪婪分布最小二乘法(greedy stepwise least squares)法。 ...

    l1范数最小化求解系数方程:正交匹配追踪法(orthogonal matching pursuit)

    本文部分参考[0]

    目录

    贪婪算法

    正交匹配追踪法是信号处理中拟合稀疏模型的一种贪婪分布最小二乘法(greedy stepwise least squares)法。

    贪婪算法(greedy algorithm)的基本思想是:不求整体最优解,而是试图尽快找到某种意义上的局部最优解。贪婪法虽然不能对所有问题得到整体最优解,但对范围相当广泛的许多问题能产生整体最优解或者整体最优解的近似解。和使用凸优化算法的l1范数相比,贪婪算法在速度上具有很大优势。典型的贪婪算法有匹配追踪法和正交匹配追踪法:

    匹配追踪法

    匹配追踪法(matching pursuit, MP) 是由法兰西大牛Mallat于1993年提出。其基本思想是,不针对某个代价函数进行最小化,而是考虑迭代地构造一个稀疏解x: 只使用字典矩阵A的少数列向量的线性组合对观测向量x实现稀疏逼近Ax=y,其中字典矩阵A被选择的列向量所组成的集合是以逐列的方式建立的。在每一步迭代,字典矩阵中通当前残差向量r=Axy中最相似的列向量被选择作为作用集的新一列。如果残差随着迭代的进行递减,则可以保证算法的收敛。

    正交匹配追踪

    匹配追踪只能保证残差向量与每一步迭代所选的字典矩阵列向量正交,但与以前选择的列向量一般不正交。正交匹配追踪(orthogonal matching pursuit, OMP)则能保证每步迭代后残差向量与以前选择的所有列向量正交,以保证迭代的最优性,从而减少了迭代次数,性能也更稳健。


    正交匹配追踪算法

    输入 观测数据向量yRm和字典矩阵ARm×n.
    输出 稀疏系数向量 xRn.
    Step 1 初始化 令标签集Ω0=,初始残差向量r0=y,令k=1.
    Step 2 辨识 求矩阵A中与残差向量rk1最强相关的列
    jkargmaxj|<rk1,ϕj>|,Ωk=Ωk1jk
    Step 3 估计 最小化问题 minxyAΩkx的解由
    xk=(AHΩkAΩk)1AHΩky给出,其中
    AΩk=[aω1,...,aωk],ω1,...,ωkΩk
    Step 4 更新残差
    rk=yAΩkxk
    Step 5k=k+1,并重复Step 2Step 4。若某个停止判据满足,则停止迭代。
    Step 6 输出系数向量
    x(i)=xk(i), if iΩk
    x(i)=0, otherwise

    注: AH为共轭转置

    下面是三种常用的停止判据
    1. 运行到某个固定的迭代步数后停止。
    2. 残差能量小于某个预先给定值ε
    rk2ε
    3. 当字典矩阵A的任何一列都没有残差向量rk的明显能量时
    AHrkε

    Matlab 实现

    function [x, Out] = OMP(A,y,varargin)
    % This is a l1 minimization solver for orthogonal matching pursuit: 
    %   minimize     ||x||_1
    %   subject to   y = Ax,
    % -----------------------------------------------------------------
    % Author: Beier ZHU
    %         Tsinghua University
    % -----------------------------------------------------------------
    % 
    % =========================Required inputs=========================  
    % A -- an m x n matrix
    % y -- an m x 1 vector
    % =========================Optional inputs=========================
    % 'maxIter' -- maximum number of iterations
    % 'StopTolerance' -- stopping tolerance
    % ===========================Outputs===============================
    % x -- last iterate (hopefully an approximate solution)
    % Out.iter -- # of iterations taken
    
        % Test for number of required parametres
        if (nargin-length(varargin)) ~= 2
            error('Wrong number of required parameters');
        end
        %--------------------------------------------------------------
        % Set parameters to their defaults
        %--------------------------------------------------------------
        opts.tol = 1e-3;
        opts.maxIter = 1e3;
        %--------------------------------------------------------------
        % Set parameters to user specified values
        %--------------------------------------------------------------
        if (rem(length(varargin),2)==1)
            error('Options should be given in pairs');
        else
            for i=1:2:(length(varargin)-1)
                switch upper(varargin{i})
                    case 'STOPTOLERANCE'
                        opts.tol = varargin{i+1};
                    case 'MAXITER'
                        opts.maxit = varargin{i+1};
                    otherwise
                        error(['Unrecognized option: ''' varargin{i} '''']);
            end
        end
        [m_A, n] = size(A);
        [m_y, n_y] = size(y);
        if n_y ~= 1
            error(['y must be a column vector']);
        end
        if m_A ~= m_y
            error(['A and y must have same # of row'])
        end
        % --------------------------------------------------------------
        x = zeros(n,1);
        Omega = [];
        A_Omega = [];
        r = y;
        iter = 1;
        varepsilon = 1e-3; % step 1
    
        while true
            [~, max_index] = max(abs(A'*r));
            Omega = [Omega max_index];
            A_Omega = [A_Omega A(:,max_index)]; % step 2
            x_k = A_Omega\y; % step 3
            r = y - A_Omega*x_k; % step 3
            iter = iter + 1; % step 4
            if (iter > opts.maxIter) || (norm(r) <= opts.tol) || (norm(A'*r, inf) <= varepsilon)
                break; % 终止条件
            end
        end  
        x(Omega) = x_k; %step 5
        Out.iter = iter;
    end
    '''

    [0]: 矩阵分析与应用 第二版 张贤达

    展开全文
  • l1范数最小化快速算法

    万次阅读 2016-01-15 00:46:55
    如果取l1l_1 范数,则是获取的bb数据,受到污染比较严重。并且bb 本身就是稀疏的。这也是人的经验对于模型的成功也是很重要的。 2:几类优化算法 (1)梯度投影算法Gradient Projection Methods

    1:解决的问题模型如下:

    这里写图片描述
    或者约束条件可以适当的松弛,即为如下模型:
    这里写图片描述
    当然约束条件取l2范数,b数据获取的比较准确,结果逼近的效果更好,防止过拟合。如果取l1 范数,则是获取的b数据,受到污染比较严重。并且b 本身就是稀疏的。这也是人的经验对于模型的成功也是很重要的。
    2:几类优化算法
    (1)梯度投影算法Gradient Projection Methods
    原问题可以变为如下问题:
    这里写图片描述
    下面介绍两种方法对其进行处理。
    i)上式又等价于:
    这里写图片描述

    这里写图片描述
    所以就有如下记号和约定:
    这里写图片描述
    更新zk 时沿着负梯度的方向下降最快。但是只是局部最小值。
    这里写图片描述
    其中ak 是步长,可以用线搜索的方法来确定最优步长。
    下介绍第二种方法 truncated Newton interior-point method.
    ii)上式又等价于:
    这里写图片描述
    利用内点法的把约束条件给罚到目标函数上去。
    在这里我们对约束条件利用logarithmic barrier函数进行改写。
    这里写图片描述
    在这里,我们可以看到当xi 越接近uiui的时候,函数值会变得越大。当xi 无限趋近于uiui时,则函数值无限趋于无穷大。所以只有当xi 趋近于0时候,函数值才趋近于一个常数。
    所以上式可以等价于如下模型:
    这里写图片描述

    然后利用牛顿算法进行求解计算。

    (2)迭代阈值收缩算法 Iterative Shrinkage-Thresholding Methods
    对于一般的模型:
    这里写图片描述
    其中:这里写图片描述

    f(x) 二次近似。则问题转变成如下:
    这里写图片描述
    可以适用迭代阈值算法。关于l_{1}范数最优化的迭代阈值算法的证明可以参见我的另一篇博客

    (3)近端梯度算法 Proximal gradient method
    其处理的模型如下:
    这里写图片描述
    其中f(x)是连续可微的,微分函数满足利普希茨条件成立:
    这里写图片描述
    其中L相当于代替f(x)的二阶偏导。
    那么可以进行如下算法来解决问题:
    这里写图片描述
    说明:
    第一步的更新:按照f(x)沿着负梯度的方向下降最快
    第二步的更新:有数值解,进行软阈值操作。
    (4)交替方向法 Alternating Direction Methods
    其实利用的是拉格朗日算法,来进行更新出来。解决的模型如下:
    这里写图片描述
    其拉格朗日函数如下:
    这里写图片描述
    问题变为分别最小化x,e,y
    说明:
    更新e时,固定x,y,直接求导,e有数值解。
    更新x 时,固定e,y经过化简,可以运用软阈值进行操作计算。
    更新y时,固定x,e,直接求导,y有数值解。

    Fast ℓ 1-minimization algorithms and an application in robust face recognition

    展开全文
  • l1范数最小化快速算法【文献阅读】

    千次阅读 2018-06-02 13:42:31
    如果取l1l1 范数,则是获取的bb数据,受到污染比较严重。并且bb 本身就是稀疏的。这也是人的经验对于模型的成功也是很重要的。 2:几类优化算法  (1)梯度投影算法Gradient Projection Methods  原问题可以...

    1:解决的问题模型如下:

    这里写图片描述 
    或者约束条件可以适当的松弛,即为如下模型: 
    这里写图片描述 
    当然约束条件取l2l2范数,bb数据获取的比较准确,结果逼近的效果更好,防止过拟合。如果取l1l1 范数,则是获取的bb数据,受到污染比较严重。并且bb 本身就是稀疏的。这也是人的经验对于模型的成功也是很重要的。 
    2:几类优化算法 
    (1)梯度投影算法Gradient Projection Methods 
    原问题可以变为如下问题: 
    这里写图片描述 
    下面介绍两种方法对其进行处理。 
    i)上式又等价于: 
    这里写图片描述

    这里写图片描述 
    所以就有如下记号和约定: 
    这里写图片描述 
    更新zkzk 时沿着负梯度的方向下降最快。但是只是局部最小值。 
    这里写图片描述 
    其中akak 是步长,可以用线搜索的方法来确定最优步长。 
    下介绍第二种方法 truncated Newton interior-point method. 
    ii)上式又等价于: 
    这里写图片描述 
    利用内点法的把约束条件给罚到目标函数上去。 
    在这里我们对约束条件利用logarithmic barrier函数进行改写。 
    这里写图片描述 
    在这里,我们可以看到当xixi 越接近ui或者−uiui或者−ui的时候,函数值会变得越大。当xixi 无限趋近于ui或者−uiui或者−ui时,则函数值无限趋于无穷大。所以只有当xixi 趋近于0时候,函数值才趋近于一个常数。 
    所以上式可以等价于如下模型: 
    这里写图片描述

    然后利用牛顿算法进行求解计算。

    (2)迭代阈值收缩算法 Iterative Shrinkage-Thresholding Methods 
    对于一般的模型: 
    这里写图片描述 
    其中:这里写图片描述

    对f(x)f(x) 二次近似。则问题转变成如下: 
    这里写图片描述 
    可以适用迭代阈值算法。关于l_{1}范数最优化的迭代阈值算法的证明可以参见我的另一篇博客

    (3)近端梯度算法 Proximal gradient method 
    其处理的模型如下: 
    这里写图片描述 
    其中f(x)f(x)是连续可微的,微分函数满足利普希茨条件成立: 
    这里写图片描述 
    其中LL相当于代替f(x)f(x)的二阶偏导。 
    那么可以进行如下算法来解决问题: 
    这里写图片描述 
    说明: 
    第一步的更新:按照f(x)f(x)沿着负梯度的方向下降最快 
    第二步的更新:有数值解,进行软阈值操作。 
    (4)交替方向法 Alternating Direction Methods 
    其实利用的是拉格朗日算法,来进行更新出来。解决的模型如下: 
    这里写图片描述 
    其拉格朗日函数如下: 
    这里写图片描述 
    问题变为分别最小化x,e,yx,e,y。 
    说明: 
    更新ee时,固定x,yx,y,直接求导,ee有数值解。 
    更新xx 时,固定e,ye,y经过化简,可以运用软阈值进行操作计算。 
    更新yy时,固定x,ex,e,直接求导,yy有数值解。

    Fast ℓ 1-minimization algorithms and an application in robust face recognition

    展开全文
  • 以前下了一个minL1.m的代码,但是不正确。自己进行了修改,现在可以正确使用。
  • 1、l1_ls_nonneg.m生成的.dll文件.h文件.lib文件。 2、将生成的三个文件放入到c++的相应的搜索目录下即可调用 3、具体的操作,我有机会会写在CSDN的博客上
  • L1范数最小正则概念解释基本原理为什么L1范数最小正则能够获得稀疏解? 概念解释 对于L1范数最小正则,我们先拆分开来解释。 L1范数:向量中各元素绝对值之和。如[1,-1,3]的L1范数为1+1+3=5。 正则:对模型...

    概念解释

    对于L1范数最小正则化,我们先拆分开来解释。
    L1范数:向量中各元素绝对值之和。如[1,-1,3]的L1范数为1+1+3=5。
    正则化:对模型提高泛化能力的一种方案。对于训练得到的模型,可能会出现模型复杂的情况,正则化可以看作对模型的简化,以提高模型适应能力。
    最小:指最小化损失函数。在我们训练模型时,通过最小化损失函数可以使模型对于训练集更为拟合。

    那么对于L1范数最小正则化的理解可以是这样的:向损失函数J中添加一个L1范数,使 J1=J+L1_norm, 将新的损失函数J1作为新的优化目标,J1最小时,能够得到具有泛化能力的模型(正则化)。

    实际上,L1范数最小正则化是一个能使训练的模型具有泛化能力,且能获得稀疏解的一种方案。

    基本原理

    首先我们假设有一组训练集:
    在这里插入图片描述
    对于这一组训练集,我们希望得到一个权重向量w,使:
    在这里插入图片描述
    在谈到拟合问题时,我们希望(yi - wTxi)尽量小,基于最小二乘法,可以构建以下方程:
    在这里插入图片描述
    对于上述方程,Jemp可以作为损失函数,在我们把Jemp作为优化目标时,优化结果为:所有训练集都能很好地拟合得到结果,但不具备泛化能力。得到的权重向量 w 并不唯一,更可能会出现 w 向量内单个维度绝对值特别大的情况,这种情况下,某个维度特征的微弱变化会引起结果病态的变化。显然,得到的结果是不具备实际意义的。

    此时,我们引入L1范数会得到什么样的改观呢?
    在这里插入图片描述
    在Jemp的基础上加上 w 的L1范数。将 J 作为优化目标,对 w 单个维度绝对值过大加入了一个“惩罚”,可以有效防止这种情况。
    另一方面,L1范数最小正则化可以获得稀疏解。即 w 的解中,很多维度的数值为0。稀疏解的存在舍弃了样本中不影响结果或者影响微弱的特征,能够有效地简化模型。(为什么能获得稀疏解在下一节介绍)

    那么,通过引入L1范数,最终得到的模型不仅能够迎合训练集,而且足够简单有效,这也就是说为什么L1范数最小正则化能够泛化模型。

    为什么L1范数最小正则化能够获得稀疏解?

    或许用一个简单的例子就能帮助我们理解了。
    假设在一个二维空间,我们有样本点 (2,2)。已知模型是线性模型。
    即:y = ax+b
    代入样本点:2 = 2a+b
    那么 a , b 作为这个模型的解,解空间为:
    b = 2 - 2 a ,解空间如图所示。b 为 y 轴。
    在这里插入图片描述
    对于这个解空间来说,可以知道,a ,b的解是不固定的。甚至 a , b的绝对值也特别大。
    而当我们引入L1范数,[a , b]视为解向量 w 。||w||1 = |a|+|b|。对于L1范数在坐标系中的表示即为如图所示的一个菱形(每个角均为90°)。
    在这里插入图片描述
    而当这个菱形与a,b的解空间有交点时,意味着引入L1范数的损失函数有解。此时,我们需要损失函数最小化,这是一个凸优化问题,在极值处可以求得解。即当菱形与蓝色直线只有一个交点时,可以得到我们的基于L1范数最小正则化的解。
    在这里插入图片描述
    那么最终我们得到的解为 a=1,b=0,最终得到的拟合模型为 y = x。其中b为0恰好某种意义满足了稀疏解的性质,这是由于L1范数本身性质,以至于当存在最优解时,这个解往往是“顶点”,而这个“顶点”,恰好满足解向量多个维度值为0的情况。(放大到多维空间也是同样的)

    那么,重申结论:L1范数最小正则化在一般情况下是能够得到稀疏解的。

    实际上,如果使用其他的范数作为辅助优化项呢?
    在这里插入图片描述
    从上图可以看出,当使用其他的Lp范数时,p值越小,顶点越尖锐。那么此时能够得到稀疏解的可能性越大。而我们为什么要使用L1范数呢,这是由于它方便计算这个性质决定的。

    展开全文
  • 基于加权l1-范数最小化的稀疏FIR滤波器设计
  • L1-L2范数最小化问题-迭代收缩算法 涉及L1-L2范数的机器学习问题非常常见,例如我们遇到的去噪、稀疏表示和压缩感知。一般而言,这类问题可以表示为: \[ \min_{\bf{z}} || {\bf{z}}||_0 \\ \text{subject to: } ~ ...
  • (L0范数很难优化求解) L1范数是指向量中各个元素绝对值之和L2范数是指向量各元素的平方和然后求平方根 L1范数可以进行特征选择,即让特征的系数变为0.L2范数可以防止过拟合,提升模型的泛化能力,有助于处理 ...
  • L1范数与L2范数的联系   最小化误差的L2范数等价于对高斯噪声的MLE。   最小化误差的L1范数等价于对拉普拉斯噪声的MLE。
  • L1范数

    千次阅读 2014-06-04 16:48:30
    通常情况下,欠定线性方程是没有唯一解的,如果加上其他的条件则可以缩小解得范围,比如加上二范数最小化这个条件,则方程可以得到最小范数解,该解唯一,我们知道二范数是能量的度量单位,它是用来度量重构误差的,...
  • 一、易混概念对于一些常见的距离先做一个简单的说明1.欧式距离假设X和Y都是一个n维的向量,即 则欧氏距离: 2.L2范数假设X是n维的特征 L2范数: 3....1. L2损失函数L2范数损失函数,也被称为最小平方误...
  • L1范数 系数表达

    千次阅读 2014-02-10 23:25:36
    通常情况下,欠定线性方程是没有唯一解的,如果加上其他的条件则可以缩小解得范围,比如加上二范数最小化这个条件,则方程可以得到最小范数解,该解唯一,我们知道二范数是能量的度量单位,它是用来度量重构误差的,...
  • 向量的范数:向量范数是定义了向量的类似于长度的性质,满足正定,齐次,三角不等式的关系就称作范数。向量的范数一般有L0, L1, L2与L_infinity范数,L0范数:...在特征选择中,通过最小化L0范数来寻找最少最优的稀疏...
  • 稀疏束调整广泛用于许多计算机视觉... 实验表明,与L2范数束调整相比,在存在异常值或Laplacian噪声的情况下,该方法对于合成生成的数据集和实际数据集均具有更好的性能,并且该方法在最新的L1最小化方法中非常有效。
  • 你必须设置你想要最小化的函数(在我们的例子中,一个平面的形式是Z=aX+bY+c)和误差函数(L1范数),然后用一些起始值运行最小值。在import numpy as npimport scipy.linalgfrom scipy.optimize import minimizefrom ...
  • L1 和 L2 都是深度学习中常用的正则化项(regularizer),描述的是模型的复杂度,它的作用在于模型越复杂,正则化项越大,将它加在损失函数(loss function)后面作为罚项(penalty),这样在最小化损失函数的过程中...
  • Matlab中CVX为什么不能求解L1范数? 最近在弄和cvx相关的一些东西,我的cvx为什么不能对1范数进行最小化优化啊? 求好心人指导!!! % 这里的x和y都是已知的 % 我想要求w的L1一范数最小值 cvx_begin variable w(N...
  • L1范数与L2范数对比

    2020-11-13 15:22:30
    L1和L2范数的比较 L0范数是指向量中非0的元素的个数。(L0范数很难优化求解) L1范数是指向量中各个元素绝对值之和 ...下降速度:最小化权值参数L1比L2变化的快 模型空间的限制:L1会产生稀疏 L2不会。 L1会趋向于产
  • 监督机器学习问题无非就是“minimize your error while regularizing your parameters”,也就是,在规则化参数的同时最小化误差。最小化误差是为了让我们的模型拟合我们的训练数据,而规则化参数是防止我们的模型...
  • 为什么最小化权重的范数就可以实现正则化?L1L1L1 范数和 L2L2L2 **范数** 有什么区别?参考:上文本人随手翻译笔记,表述不足或错误之处欢迎批评指正 深度学习基础:L1正则化,L2正则化与范数的关系? L1L1L1 正则...
  • 声明:版权所有,转载请...监督机器学习问题无非就是“minimize your error while regularizing your parameters”,也就是在规则化参数的同时最小化误差。最小化误差是为了让我们的模型拟合我们的训练数据,而规则化
  • 原文链接地址:http://blog.csdn.net/zouxy09/article/details/249728691.监督学习的基本模型监督机器学习问题无非就是...最小化误差是为了让我们的模型拟合我们的训练数据,而规则化参数是防止我们的模型过分拟合我...
  • 在练习机器学习时,可能会选择决定是使用L1范数还是L2范数进行正则化,还是作为损失函数等。 L1范数也称为最小绝对偏差(LAD),最小绝对误差(LAE)。它基本上是最小化目标值(Yi)和估计值(f(xi))之间的绝对...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 222
精华内容 88
关键字:

l1范数最小化