1.什么是稀疏表示用较少的基本信号的线性组合来表达大部分或者全部的原始信号。其中这些基本信号被称作原子是从过完备字典中选出来的而过完备字典则是由个数超过信号维数的原子聚集而来的。可见任一信号在不同的原子组下有不同的稀疏表示。假设我们用一个M*N的矩阵表示数据集X每一行代表一个样本每一列代表样本的一个属性一般而言该矩阵是稠密的即大多数元素不为0。 稀疏表示的含义是寻找一个系数矩阵A(K*N)以及一个字典矩阵B(M*K)使得B*A尽可能的还原X且A尽可能的稀疏。A便是X的稀疏表示。​编辑南大周志华老师写的《机器学习》这本书上原文“为普通稠密表达的样本找到合适的字典将样本转化为合适的稀疏表达形式从而使学习任务得以简化模型复杂度得以降低通常称为‘字典学习’(dictionary learning)亦称‘稀疏编码’(sparse coding)”块内容。表达为优化问题的话字典学习的最简单形式为\\ 其中xi为第i个样本B为字典矩阵αi为xi的稀疏表示λ为大于0参数。•寻找少量重要的系数来表示原始信号的技术被称作Sparse Coding(稀疏编码或稀疏分解)•从任意一个字典中为原始信号寻找最稀疏的表示常用的方法分类两类①贪婪算法比如匹配追踪(MP)、正交匹配追踪(OMP)、弱匹配追踪(WMP)、阈值方法等②松弛算法比如迭代加权最小二乘(Iterative-Reweighed-Least-SquaresIRLS)、基追踪(BP)等。其中贪婪算法的特点是速度快精度相对较低松弛算法是精度高但速度慢。•穷举法——NP难假设 的非零项数目为L(sparse level)先令L1字典里的每一个原子(列向量)尝试一遍看是否满足终止条件共有K种组合。如果没有满足再令L2再次尝试共有K(K-1)/2种组合。还没有满足条件的则令L3……组合的数目呈指数增长于是遇到了NP难问题。•贪婪算法——Matching Pursuit第一步找到最接近X的原子等效于 向量上仅取一个非零项求出最接近的原子保留下来第二步计算误差是否满足要求如果满足算法停止否则计算出残差信号和第一步类似找到最接近残差向量的原子保留下来第三步调整已选向量的系数使得 最接近X重复第二步。•松弛算法——Basis Pursuit将L0问题转化为L1问题解决的方法有很多比如内点法、迭代收缩法等。事实上它可以化成一个线性规划的问题用MATLAB很容易解。上式中第一个累加项说明了字典学习的第一个目标是字典矩阵与稀疏表示的线性组合尽可能的还原样本第二个累加项说明了αi应该尽可能的稀疏。之所以用L1范式是因为L1范式正则化更容易获得稀疏解。具体原因参看该书11.4章或移步机器学习中的范数规则化之(一)L0、L1与L2范数。字典学习便是学习出满足上述最优化问题的字典B以及样本的稀疏表示A(A{α1α2…αi})。L1正则化常用于稀疏可以获得稀疏解。如下图表示L1正则化交点在轴上所得的解一般只是在某个轴上有实数另外的轴为0从而最终得到稀疏解。2.字典学习寻找字典的过程称为字典学习。字典学习的一个假设是字典对于指定信号具有稀疏表示。因此选择字典的原则就是能够稀疏地表达信号。两种方法来设计字典:•从已知的变换基中选取比如 DCT 、小波基等这种方法很通用但是不能自适应于信号。学习字典即通过训练和学习大量的与目标数据相似的数据来获得。这里我们介绍一种叫K-SVD的方法字典学习算法理论包含两个阶段字典构建阶段(Dictionary Generate)和利用字典(稀疏的)表示样本阶段(Sparse coding with a precomputed dictionary)。这两个阶段(如下图)的每个阶段都有许多不同算法可供选择每种算法的诞生时间都不一样以至于稀疏字典学习的理论提出者已变得不可考。笔者尝试找了Wikipedia和Google Scolar都无法找到这一系列理论的最早发起人。出处http\://www.mamicode.com/info-detail-1568956.html字典学习的第一个好处——它实质上是对于庞大数据集的一种降维表示。第二正如同字是句子最质朴的特征一样字典学习总是尝试学习蕴藏在样本背后最质朴的特征(假如样本最质朴的特征就是样本最好的特征).稀疏表示的本质用尽可能少的资源表示尽可能多的知识这种表示还能带来一个附加的好处即计算速度快。我们希望字典里的字可以尽能的少但是却可以尽可能的表示最多的句子。这样的字典最容易满足稀疏条件。也就是说这个“字典”是这个“稀疏”私人订制的。稀疏表达有两点好处\ 1) 省空间\ 2) 奥卡姆剃刀说如果两个模型的解释力相同选择较简洁的那个。稀疏表达就符合这一点。How to find the dictionary D?——K-SVD假设现在有原始信号矩阵 该矩阵的每一行表示一个信号或者一张图片 D 矩阵是字典矩阵右下方是 稀疏解矩阵S红色的点表示非零项。​编辑Step 1: Initialize. 在 矩阵中随机挑选一些行向量(一些原图)填满矩阵 D并归一化每一列。Step 2: Sparse Coding. 用松弛或者贪婪法进行稀疏编码使得​编辑得到稀疏表示 构成稀疏矩阵S的第i行。What are sparse representations/approximations good for?•稀疏性是DFT、WT和SVD分解得以广泛利用的原因之一这些变换的目的都是为了反映信号的确定性结构并用紧凑的或稀疏的表示来表征这些结构•稀疏表示的思想为模式分类方法建立了基础比如SVM和RVM其中稀疏性直接与估计函数(estimator)的学习能力有关。•稀疏表示解决的问题主要集中在•图像去噪(Denoise)代表性paperImage Denoise Via Sparse and Redundant Representations Over Learned Dictionaries(Elad M. and Aharon M. IEEE Trans. on Image Processing,Dec,2006);Image Sequence Denoising Via Sparse and Redundant Representations(Protter M. and Elad M.IEEE Trans. on Image Processing,Jan,2009)•超分辨率重建(Super-Resolution OR Scale-Up)代表性paperImage Super-Resolution via Sparse Representation(Jianchao Yang, John Wright, Thomas Huang, and Yi MaIEEE Transactions on Image Processing, Nov,2010),A Shrinkage Learning Approach for Single Image Super-Resolution with Overcomplete Representations( A. Adler, Y. Hel-Or, and M. Elad,ECCV,Sep,2010);另外还有inpainttingdeblurringcompression等等..更多应用参考Elad M的书。​编辑​编辑 % % Simple demo codes for image super-resolution via sparse representation % % Reference % J. Yang et al. Image super-resolution as sparse representation of raw % image patches. CVPR 2008. % J. Yang et al. Image super-resolution via sparse representation. IEEE % Transactions on Image Processing, Vol 19, Issue 11, pp2861-2873, 2010 %% clear all; clc;% read test image im_l imread(Data/Testing/input.bmp);% set parameters lambda 0.2; % sparsity regularization overlap 4; % the more overlap the better (patch size 5x5) up_scale 2; % scaling factor, depending on the trained dictionary maxIter 20; % if 0, do not use backprojection% load dictionary load(Dictionary/D10240.15_5.mat);% change color space, work on illuminance only imlycbcr rgb2ycbcr(iml); imly imlycbcr(:, :, 1); imlcb imlycbcr(:, :, 2); imlcr iml_ycbcr(:, :, 3);% image super-resolution based on sparse representation [imhy] ScSR(imly, 2, Dh, Dl, lambda, overlap); [imhy] backprojection(imhy, imly, maxIter);% upscale the chrominance simply by bicubic [nrow, ncol] size(imhy); imhcb imresize(imlcb, [nrow, ncol], bicubic); imhcr imresize(imlcr, [nrow, ncol], bicubic);imhycbcr zeros([nrow, ncol, 3]); imhycbcr(:, :, 1) imhy; imhycbcr(:, :, 2) imhcb; imhycbcr(:, :, 3) imhcr; imh ycbcr2rgb(uint8(imh_ycbcr));% bicubic interpolation for reference imb imresize(iml, [nrow, ncol], bicubic);% read ground truth image im imread(Data/Testing/gnd.bmp);% compute PSNR for the illuminance channel bbrmse computermse(im, imb); sprmse computermse(im, imh);bbpsnr 20*log10(255/bbrmse); sppsnr 20*log10(255/sprmse);fprintf(PSNR for 双立方插值: %f dB\n, bbpsnr); fprintf(PSNR for 稀疏表示: %f dB\n, sppsnr);% show the images figure, imshow(imh); title(稀疏表示); figure, imshow(imb); title(双立方插值); ​ 部分理论引用网络文献若有侵权联系博主删除 关注我领取海量matlab电子书和数学建模资料 各类智能优化算法改进及应用生产调度、经济调度、装配线调度、充电优化、车间调度、发车优化、水库调度、三维装箱、物流选址、货位优化、公交排班优化、充电桩布局优化、车间布局优化、集装箱船配载优化、水泵组合优化、解医疗资源分配优化、设施布局优化、可视域基站和无人机选址优化、背包问题、 风电场布局、时隙分配优化、 最佳分布式发电单元分配、多阶段管道维修、 工厂-中心-需求点三级选址问题、 应急生活物质配送中心选址、 基站选址、 道路灯柱布置、 枢纽节点部署、 输电线路台风监测装置、 集装箱调度、 机组优化、 投资优化组合、云服务器组合优化、 天线线性阵列分布优化、CVRP问题、VRPPD问题、多中心VRP问题、多层网络的VRP问题、多中心多车型的VRP问题、 动态VRP问题、双层车辆路径规划2E-VRP、充电车辆路径规划EVRP、油电混合车辆路径规划、混合流水车间问题、 订单拆分调度问题、 公交车的调度排班优化问题、航班摆渡车辆调度问题、选址路径规划问题、港口调度、港口岸桥调度、停机位分配、机场航班调度、泄漏源定位 机器学习和深度学习时序、回归、分类、聚类和降维2.1 bp时序、回归预测和分类2.2 ENS声神经网络时序、回归预测和分类2.3 SVM/CNN-SVM/LSSVM/RVM支持向量机系列时序、回归预测和分类2.4 CNN|TCN|GCN卷积神经网络系列时序、回归预测和分类2.5 ELM/KELM/RELM/DELM极限学习机系列时序、回归预测和分类2.6 GRU/Bi-GRU/CNN-GRU/CNN-BiGRU门控神经网络时序、回归预测和分类2.7 ELMAN递归神经网络时序、回归\预测和分类2.8 LSTM/BiLSTM/CNN-LSTM/CNN-BiLSTM/长短记忆神经网络系列时序、回归预测和分类2.9 RBF径向基神经网络时序、回归预测和分类2.10 DBN深度置信网络时序、回归预测和分类2.11 FNN模糊神经网络时序、回归预测2.12 RF随机森林时序、回归预测和分类2.13 BLS宽度学习时序、回归预测和分类2.14 PNN脉冲神经网络分类2.15 模糊小波神经网络预测和分类2.16 时序、回归预测和分类2.17 时序、回归预测预测和分类2.18 XGBOOST集成学习时序、回归预测预测和分类2.19 Transform各类组合时序、回归预测预测和分类方向涵盖风电预测、光伏预测、电池寿命预测、辐射源识别、交通流预测、负荷预测、股价预测、PM2.5浓度预测、电池健康状态预测、用电量预测、水体光学参数反演、NLOS信号识别、地铁停车精准预测、变压器故障诊断图像处理方面图像识别、图像分割、图像检测、图像隐藏、图像配准、图像拼接、图像融合、图像增强、图像压缩感知 路径规划方面旅行商问题TSP、车辆路径问题VRP、MVRP、CVRP、VRPTW等、无人机三维路径规划、无人机协同、无人机编队、机器人路径规划、栅格地图路径规划、多式联运运输问题、 充电车辆路径规划EVRP、 双层车辆路径规划2E-VRP、 油电混合车辆路径规划、 船舶航迹规划、 全路径规划规划、 仓储巡逻 无人机应用方面无人机路径规划、无人机控制、无人机编队、无人机协同、无人机任务分配、无人机安全通信轨迹在线优化、车辆协同无人机路径规划 通信方面传感器部署优化、通信协议优化、路由优化、目标定位优化、Dv-Hop定位优化、Leach协议优化、WSN覆盖优化、组播优化、RSSI定位优化、水声通信、通信上传下载分配 信号处理方面信号识别、信号加密、信号去噪、信号增强、雷达信号处理、信号水印嵌入提取、肌电信号、脑电信号、信号配时优化、心电信号、DOA估计、编码译码、变分模态分解、管道泄漏、滤波器、数字信号处理传输分析去噪、数字信号调制、误码率、信号估计、DTMF、信号检测电力系统方面微电网优化、无功优化、配电网重构、储能配置、有序充电、MPPT优化、家庭用电 元胞自动机方面交通流 人群疏散 病毒扩散 晶体生长 金属腐蚀 雷达方面卡尔曼滤波跟踪、航迹关联、航迹融合、SOC估计、阵列优化、NLOS识别 车间调度零等待流水车间调度问题NWFSP、置换流水车间调度问题PFSP、混合流水车间调度问题HFSP、零空闲流水车间调度问题NIFSP、分布式置换流水车间调度问题 DPFSP、阻塞流水车间调度问题BFSP