1、大数据与数学研究大数据与数学研究目录目录第一部分大数据及其面临的挑战第二部分大数据分析与处理中的关键科学问题第三部分关于若干大数据科学问题的研究第四部分结语什么是大数据？什么是大数据？数据数据l历史的记录、交易的轨迹、过程的监控、 经验的累积、l数据: 以编码形式存在的信息载体，是真实世界的碎片化反映记录文件报告表格视频图片歌曲ZB（1021）,EB（1018）,PB（1015）,TB（1012）,GB（109）,MB（106）数据的常见形式什么是大数据？什么是大数据？常规定义常规定义大数据是指无法在容许的时间内用常规的软件工具对其内容进行抓取、管理和处理的数据集合，大数据规模的标准是持续变化
2、的，当前泛指单一数据集的大小在十几TB和PB之间。（维基百科）l 具有数量大、增长快、类型多、价值密度低等4V特征的数据集。Volumel PBZB 量级l 不可能集中存储l 不可能集中处理l 动态增长、时变l 以数据流呈现，有时 效性l 形式、来源多样l 冗余、不完全并存l 非结构化 l 存在大价值l 但依赖整体 l 价值密度低VelocityVarietyValue大数据=现有数据处理技术难以处理的超大规模数据什么是大数据？什么是大数据？泛化定义泛化定义泛指一个时代、一项技术、一种文化、一个挑战。（通常也是大数据集、大数据技术与大数据应用的总称）拥有大数据是时代特征、解读大数据是时代任务、
3、应用大数据是时代机遇！（大数据时代）能够对复杂海量数据进行实时获取、传输、存储、加工和利用的高新技术！（大数据技术）我们信奉上帝，除了上帝任何人都要以数据说话！（大数据文化）现有的数据采集、传输、存储、处理与分析技术己无法适用于现有的需要！（大数据挑战）什么是大数据？什么是大数据？更本质的定义更本质的定义“大”是一个相对的概念反映真实世界的数据（碎片）其量己达到可以从一定程度上反映其真实面貌的程度。大数据（量变 质变）为什么大数据会热？为什么大数据会热？是必然还是炒作？是必然还是炒作？数字化(Digitization) 数据化(Datafication)物联网作为联接人、机、环境的基本交互方式
4、大数据处理与分析是信息处理的基本形式新一轮信息技术革命互联网、云存储作为基本的基础设施服务计算作为计算机应有的基本模式l 新一轮信息技术革命与人类社会经济活动交汇融合必然产生大数据；l 大数据从信息载体这一底层 (一个更普适、更本质的角度)捕捉到了信息化的共性基础、未来发展与普适技术。大数据及其面临的挑战大数据及其面临的挑战 发展大数据技术是国家战略重要性：社会媒体、人口流动、居住交通数据交通流、医疗、商业、环境、劳动力等数据医疗、医保、健康、影像等大数据环境、气象、交通、社会发展等大数据突发事件预测、关键人群监测城市智慧管理环境治理医疗诊断方案大数据技术：有关如何收集、整理（存储）、解读和应
5、用大数据的理论与方法l 大数据技术是解决众多国家重大现实需求问题的共性基础大数据及其面临的挑战大数据及其面临的挑战l 大数据技术是一个国家创新能力的核心要素及核心竞争力指标：它能帮助人们从大数据中发现新知识，创造新价值，形成新理念，因而是认知世界与改 造 世 界 的 能 力 （即国家创新驱动发展的一种能力） 大数据具有重大的科学社会经济价值价值：大数据及其面临的挑战大数据及其面临的挑战 在大数据技术中，分析与处理是核心核心：数据是基础、平台是支撑、分析是核心、效益是根本领域科学问题一：大数据资源管理与公共政策领域科学问题二：大数据高效获取、 存储、调用与处理的信息技术领域科学问题三大数据分析与
6、处理的统计学与计算基础领域科学问题四大数据工程（结合领域的大数据应用)数据获取与数据管理数据存储与处理数据分析与理解结合领域的大数据应用l 大数据技术需要多学科综合研究数据价值(MIT Technology Review, 2015)大数据及其面临的挑战大数据及其面临的挑战统计（电商、语音识别等）查询（google翻译、风险、信用评估等等）比对（电商等）排序（网页排序、推荐系统等）融合（互联网）预处理（对齐、配准、标准化等）发展趋势预测（负荷预测等）共性结构发现（电力客户细分等）模式识别（设备故障诊断等）关联性（设备交叉故障等）关键要素分析（售电量影响因素分析等）优化与控制（电力调度等）处理分
7、析大数据及其面临的挑战大数据及其面临的挑战l 聚焦大数据分析与处理具有紧迫性 据IDC统计数据显示，中国目前拥有的数据量占全球的14%（己收集），但数据利用率不到0.4%，大量的数据“沉睡”在各个角落，未发挥应有作用。大数据大分析大垃圾大价值公众要的是答案、不是数据！大数据及其面临的挑战大数据及其面临的挑战分析目标的改变数据特征的改变中小规模、固定尺寸、非时变、单一结构、集中存储超大规模、分布存储、流数据、超高维、多源异构等；寻找统计规律，因果分析为主关联性分析，支持智能决策l 样本等于母体？l 相关性能替代因果性？l 大数据推出来的才是真的？l 数据足够多可代替理论？ Big Data or
8、 Big Mistake？- Financial times,2014- Science,2014认识论上的困惑（从数据到模式、从模式到知识、从知识到决策每一个阶段都需要猜想、假设和理论的支撑）！ 认识论上的困惑 挑战一：方法论上的冲击l 分析基础被破坏（统计学基础、计算理论基础、逻辑等）l 计算模式受拷问（异构环境下的多粒度分布并行计算）l 处理算法不可用（必须采用新计算模式，形成新方法论）l 真伪性更加难以判定（基础不牢，地动山摇！）大数据及其面临的挑战大数据及其面临的挑战l 独立同分布被破坏l 大数定理和中心极限定理的条件（样本数 维数） D. Lazer, et al., The Pa
9、rable of Google Flu: Traps in Big Data Analysis, Science, 2014Google Flu Trends: 大量误报流感爆发规模。(Estimating high 100 out of 108 weeks)l P值检验的基础被破坏 Statically Hypothesis Inference Testing (SHIT!). 对于一大类问题应用，P = 0.01 导致11%的误报率； 而P = 0.05 导致29%的误报率！ R. Nuzzo, Statistical Errors, Nature, 2014 方法论上的冲击挑战二：立项依
10、据立项依据（为什么聚焦分析与处理？）（为什么聚焦分析与处理？）谣言比真理多、科学内涵的探讨少、局部有进展（偏重架构、应用与实践方面探索），但缺少对科学问题的系统研究。核心基础和共性技术尚未建立起来。国内外处于同一水平。l以压缩感知为代表的处理高维数据的稀疏性理论与方法（L1, L1/2, SCAD）l以卷积神经网络为代表的深度学习算法(尤其对于图像大数据)l以经验级联贝叶斯(EHB)方法为代表的多粒度并行计算模式和结构发现方法l以hadoop、spark、神经计算机为代表的分布式计算架构l以排序与搜索、排序学习、参数服务器等为基础的互联网应用实现全球首部稀疏微波成像验证性原理样机深度网络 对于
11、上述挑战性问题，近年来科学界与产业界都开展了广泛的探索与实践，取得一批令人振奋的结果。 动态：大数据及其面临的挑战 聚焦大数据分析与处理的核心基础与共性关键技术研究，力求在分析基础、处理算法、真伪性判定、结合典型领域的示范应用等方面取得突破，为各行各业大数据应用提供科学支撑和共性技术支撑。 国家应有大数据重大战略对策建议：大数据及其面临的挑战l 切入好：大数据技术涉及方方面面，但分析与处理是核心。经过近几年的“期望膨胀期”之后的冷思考，对其中科学问题有了更准确的把握，对研究方法有了初步尝试 有了开展研究的基础。大数据及其面临的挑战l 机遇多：数据分析与处理是中国人擅长领域，有优良传统和较深厚的
12、积累，尤其是通过近年来的反复研讨与实践，对解决大数据分析中关键科学问题有了一些新的解决思路，再加之，国家重视、产业倒逼都是难得机遇，为该领域的突破带来了可能 有了取得突破的可能。“在大数据科学平台、干细胞与再生医学等满足国家重大需求的领域方向、我国可能实现重大科技突破的领域以及世界可能发生重大科技事件的领域加快或加强重大科技布局”。认为大数据科学平台是满足国家重大需求的领域方向和我国可能实现重大科技突破的领域。良好积累，有取得突破、占据领先的可能中央重视，有体制优势产业倒逼，有创新驱动的原始驱动力大数据及其面临的挑战l 正当时：“研究大数据、投资大数据”已是当下蜂踴而至、热情至高的价值取向与选
13、择。谁为如此高涨的大众热情负责？解决大数据发展基础与共性技术问题，引导大数据产业健康可持续发展是国家责任。NSFC应有的承担 学界期盼为此共同努力！目录目录第一部分大数据及其面临的挑战第二部分大数据分析与处理中的关键科学问题第三部分关于若干大数据科学问题的研究第四部分结语大数据关键科学问题大数据关键科学问题（挑战的进一步分析）（挑战的进一步分析）方法论上的冲击l 分析基础被破坏（统计学基础、计算理论基础、逻辑等）l 计算模式受拷问（异构环境下的多粒度分布并行计算）l 处理算法不可用（必须采用新计算模式，形成新方法论）l 真伪性更加难以判定（基础不牢，地动山摇！）挑战一挑战二挑战三分析基础被破坏
14、处理模式需革新决策应用缺基础挑战一（分析基础被破坏）l 统计学基础被破坏 (Nature,2014)l 计算理论必须重建n 对大数据计算如何定义可解？n 对大数据计算如何区别难和易？n 对大数据如何度量计算复杂性? (时间十存储十通讯十能耗?)基于线性的相关性不再能完全刻画随机变量之间的相关；破坏表示基底的无关性假设 破坏建模f(x,y,z)中对x,y,z的独立性假设！数据可能随时间变化（ ）, 具有了生命周期且活性发生变化，分析结果（如聚类 Cluster( )）对t具有某种稳定性吗？(t)D(t)D目标一科学问题一大数据分析与处理的统计学与计算基础 在大数据分析与处理的统计学与计算基础方面
15、取得突破性进展，建立起若干新的理论，推动形成数据科学的基础理论体系。以线性回归为例, 中 对于高维未必总是成立（原因：高维时 难保证 与X中某些分量不相关；或者在线性相关的意义下，所选变量X无法完全刻画响应） 变量选择与预测失效！ Y=aTX+e E(Xe)= 0 X=(x1,x2,xp)e破坏p/n-0的假设（典型例子：DNA的维度p=30亿碱基对，样本个数n = 病人数，显然p/n为很大的数，并不趋于0！） 大数定律和中心极限定理不再成立！大数据关键科学问题大数据关键科学问题（挑战的进一步分析）（挑战的进一步分析）挑战二（处理模式需革新）n 环境：单一结构（CPU，MIC） 混合结构（CP
16、UGPUMIC共存协作计算）n 程序：串行程序设计 MPI并行 多粒度异构分布并行 n 模式1：计算密集型 数据密集型 混合型（计算密集型数据密集型）n 模式2：传统并行 分布式并行l 计算模式更新l 传统算法失效n 分布式计算可行吗？ n 解什么时候可组装？n 流数据如何高效处理？n 随机计算高效吗？n 异构并行可靠吗？ （大数据基础算法）基于基于Hadoop的处理可行吗？所出现的几个算的处理可行吗？所出现的几个算法并没有理论上的可行性支持！法并没有理论上的可行性支持！X X1 1X X2 2X X3 3X Xn n随机机制随机机制D1DkDm.聚合聚合机制机制1f2fmff目标二科学问题二
17、大数据分析与处理的新型计算模式与高效算法 提出适应异构计算环境下多粒度分布并行计算模式的系列高效算法（大数据算法），形成大数据处理的领先核心技术。大数据关键科学问题大数据关键科学问题（挑战的进一步分析）（挑战的进一步分析）目标三科学问题三挑战三（决策应用缺基础）面向典型领域的基于大数据的科学发现及其方法论依据 在国家重大需求的若干典型领域，形成大数据分析与处理的行业核心技术，促进相应领域科学发现新模式的形成，推动各行各业利用大数据的能力与水平。n 大数据行业应用需求旺盛，但缺乏有效的共性技术支撑与理论指导；n 基于大数据的科学发现（所谓的第四范式）仍缺乏有效的方法论支撑与理论基础；n 基于大数
18、据的科学发现真伪性判定更加困难l 决策分析少基础 （Financial Times，14）n 以查询、简单模型为基础的大数据决策方式其逻辑基础何在？n 如何评价其有效性、可靠性？l 行业应用缺支撑大数据关键科学问题大数据关键科学问题（挑战的进一步分析）（挑战的进一步分析）大数据关键科学问题大数据关键科学问题 如何从大数据中获取知识、支撑决策、赢得价值？ l支持大数据分析与处理的统计学基础与计算基础；l大数据分析与处理的新型计算模式与高效算法；l面向典型领域的基于大数据的科学发现及其方法论依据。科学问题科学问题（1个中心个中心3个问题）个问题） 数据表示与数据建模 分析理论与分析方法 计算模式与
19、计算方法 决策分析与真伪评价 主要研究大数据的高效表示及相应的计算建模方法论：主要研究内容1： 大数据表示与大数据建模 l 大数据的表示理论与方法（新型编码、基于特征的表示、隐结构表示、异构数据的统一表示）l 大数据抽样理论（对样本总体的推断、数据的集约表示、支持分布随机处理的抽样理论）l 稀疏建模的理论与方法（高阶、非线性稀疏性理论与方法）l 高维数据建模的理论与方法（降维、高维统计推断等）l 高不确定性数据的建模（统计、概率、逻辑、认知模型等）1大数据关键科学问题大数据关键科学问题 主要研究大数据分析的统计学、计算理论基础与共性分析方法等：主要研究内容2： 大数据分析理论与大数据分析方法
20、l 大数据分析的统计学新理论（相关性问题、伪相关问题、超高维问题、内生性问题、稳定性问题等）l 大数据计算的复杂性理论（重建可解性理论、复杂性理论、设计可行近似算法等）l 大数据机器学习与数据挖掘新方法（针对流数据、分布式数据、超高维数据、高度不确定性数据的基础算法，等）l 大数据可视分析方法（高维特征提取、几何空间化方法等）2大数据关键科学问题大数据关键科学问题 主要研究分布式环境下的大数据分析与处理的新型计算模式与基础算法：主要研究内容3： 大数据计算模式与大数据计算方法 l 分布实时计算问题(分布并行的计算架构与编程新模型、分布式计算的可行性理论、大数据算法设计等)l 现代超算问题(异构
21、计算环境下的计算优化、多粒度分布式并行环境下的新编程模型、大数据超算算法等)l 非结构化信息处理(异构数据的统一表示与分析方法、基于认知的非结构化信息处理方法等)l 多源异构信息融合(多模态异构数据的融合表示与推理、多母体数据的统计推断、跨领域迁移学习等)3大数据关键科学问题大数据关键科学问题 结合典型领域，验证并展示所发展的新理论与新方法的有效性，形成相应领域基于数据科学发现的方法论：主要研究内容4： 大数据决策分析与结果真伪评价 l 基于大数据分析决策的逻辑基础l 大数据科学发现的可证实性方法与验证方法l 典型领域的基于大数据的科学发现：4n 社会安全（基于多源数据融合的群体监测与事件发现
22、） n 医疗健康（医疗影像数据分析处理、医保与体检数据分析）n 电力调控（市场环境下电网运营、运行、调度策略）n 高铁安全（高铁运行监控、安全态势评估等）大数据关键科学问题大数据关键科学问题 解决若干统计学基础、计算理论基础方面的关键问题；提出一批新概念、新理论和新方法，形成数据科学基础理论体系。 创立大数据算法设计方法学，提出大数据分析与处理的系列基础算法，形成具有独立自主知识产权的核心技术族。 选择23个国家重大需求牵引的典型领域，提出大数据问题解决系统方案并在应用上取得突破，形成领域相关的科学发现新模式与行业应用核心技术。大数据分析基础大数据处理算法大数据应用示范大数据关键科学问题大数据
23、关键科学问题（期望突破）（期望突破） 提出大数据相关性新度量; 提出并发展稀疏性超高维统计推断和检验新理论; 建立伪相关判定准则和基于内生性的超高维统计建模理论; 提出流数据、分布数据情形下的可解性与难解性理论及方法。 在异构分布式计算模式下，系统建立聚类、分类、回归、相关性分析、大规模线性代数问题求解等大数据处理基础算法。 在国家安全、医疗健康、电力调控、高铁安全等国家重大需求领域， 应用大数据技术取得突破性成果，形成领域相关的科学发现新模式与行业应用核心技术。 大数据分析基础大数据处理算法大数据应用示范大数据关键科学问题大数据关键科学问题（期望突破）（期望突破）目录目录第一部分大数据及其面
24、临的挑战第二部分大数据分析与处理中的关键科学问题第三部分关于若干大数据科学问题的研究第四部分结语关于若干大数据科学问题的研究关于若干大数据科学问题的研究 大数据分析与处理是传统统计学分析、智能信息处理（机器学习、数据挖掘）、数据库技术的延伸和发展。在这些领域，国内己经形成了一批优势的研究群体，并取得一批国际领先/先进水平的研究成果。马志明院士徐宗本院士鄂维南院士李国杰院士高文院士李未院士关于若干大数据科学问题的探索关于若干大数据科学问题的探索西安交大课题组的研究l 超高维问题：稀疏建模理论与方法l 大数据算法设计问题：方法论与分布式计算l 非结构化信息处理问题：视觉模拟算法关于超高维问题大数据
25、超高维问题大数据超高维问题大数据超高维问题：“决策要素（）伴随大数据规模(n)呈现更高量级”所引起的解的不适定性与经典统计推断失效问题。经典统计学：np;高维问题：pn; 大数据高维问题：p=O(exp(n), n -.y=b1x1+b2x2+,bpxp线性模型:数据：D=(x1,y1),(x2,y2),(xn,yn)p 基本科学问题 l如何补足信息使问题可解?l高维统计推断l超高维数据的低维特征表示 研究热点：利用稀疏性先验（压缩感知、低秩分研究热点：利用稀疏性先验（压缩感知、低秩分解、高阶与非线性稀疏）解、高阶与非线性稀疏）关于高维问题的研究关于高维问题的研究（稀疏性先验）（稀疏性先验）（
26、典则）稀疏性：信息表示的普遍属性。意指：一个观测中感兴趣的信息表示的普遍属性。意指：一个观测中感兴趣的信息单元在整个单元中仅占少数部分的性质。通常用表示向量信息单元在整个单元中仅占少数部分的性质。通常用表示向量x x的非的非零元素个数零元素个数 刻画。刻画。稀疏信号稀疏信号稀疏图像稀疏图像稀疏稀疏SAR场景场景0.20.40.60.811.21.41.61.82x 104-30-25-20-15-10-505101520422 10 , #:10288inix=240, #:1021403inix=280, #:1006804inix= x0 xs x(线性)变换稀疏性：信息表示中更为普遍的属
27、性，指在某个线性：信息表示中更为普遍的属性，指在某个线性变换变换A下，下，Ax具有典则稀疏性。具有典则稀疏性。( (用用 来刻画来刻画) ) Ax0关于高维问题的研究关于高维问题的研究（稀疏性先验）（稀疏性先验）社交网络社交网络语义分析语义分析结构稀疏性：以某种结构方式所呈现的稀疏性。主要用于刻画属性间的相依关系：以某种结构方式所呈现的稀疏性。主要用于刻画属性间的相依关系，是处理多视角、多通道信息融合的重要工具之一。，是处理多视角、多通道信息融合的重要工具之一。,/(| )= iipqjp qgGj gq ppq pxxBx,p qx结构稀疏度量：结构稀疏度量：组间稀疏组间稀疏(q范数范数)，
28、组内合作，组内合作(p范数范数)特征提取特征提取基因序列分析基因序列分析01,1qpJenatton 2010关于高维问题的研究关于高维问题的研究（稀疏性先验）（稀疏性先验）关于高维问题的研究关于高维问题的研究（稀疏性先验）（稀疏性先验）非线性稀疏性: 线性变换（表示）稀疏性向非线性的推广，即在线性变换（表示）稀疏性向非线性的推广，即在某个非线性变换某个非线性变换T下，下，T(x)具有稀疏性（用具有稀疏性（用 刻画）。刻画）。 1W2x 13y 3W2N1N2W稀疏神经元响应稀疏神经元响应(Barlow, 1979; Roland,1993)响应稀疏性响应稀疏性非线性变换稀疏非线性变换稀疏33
29、2211()()iF WWWW x=0( )T xl 压缩感知压缩感知l 图像处理图像处理l 特征提取特征提取l 机器学习机器学习 l 地震信号处理地震信号处理l 稀疏信息处理稀疏信息处理：涉及具有稀疏性的信息源的信息处理。涉及具有稀疏性的信息源的信息处理。稀疏性问题：稀疏性问题：一个一个与大量疑似要素相关但本质上仅由少量要素决定的问题。与大量疑似要素相关但本质上仅由少量要素决定的问题。 minxT(x)0s.t.y=F(x)+e稀疏性问题模型稀疏性问题模型: :关于高维问题的研究关于高维问题的研究（稀疏性问题）（稀疏性问题） minxx0s.t.y=Ax+e特殊情形特殊情形信息获取模型信息获
30、取模型220min |xyAxx+221min |xyAxx+L L0 0框架框架L L1 1框架框架（S.Mallat (1993), J.A.Tropp & D.Needell (2007,2009)等）等）挑战与问题挑战与问题l 只在很严格的条件下才有只在很严格的条件下才有L1/L0 等价性等价性（Donoho,2006）；l L1框架不能保证在最少采样下完全重构信号；框架不能保证在最少采样下完全重构信号；l L1理论对于正规化约束（理论对于正规化约束（ ） 问题失效问题失效.121nxxx+=（Donoho(1994, 2006), R.Tibshirani (1996), Cande
31、s, Tao & Romberg (2006)等）等）L1范数是范数是L0范数的凸包络范数的凸包络关于高维问题的研究关于高维问题的研究（解决思路）（解决思路）稀疏性问题传统解决思路稀疏性问题传统解决思路基于基于 Banach 几何启示及几何启示及Lq/L0的等价性研究（相位图方法），徐宗本的等价性研究（相位图方法），徐宗本等提出了等提出了L1/2正则化框架正则化框架 （Xu, Proc. ICM，2010）。 minxRNF(x)+|x|1/21/2L1/2框架框架( )kL0( )L1( )L2( )Lsparsestsparsenot sparsenot sparse？NP problem
32、non-smooth convexsmooth and convexhard to solve( )kL( )L Banach几何启示几何启示 相位图研究相位图研究sufficiently sparse1/ 2()Lnon-convex关于高维问题的研究关于高维问题的研究（创新思路）（创新思路）如果q=1/2, F是-Lipschitz 连续， . 则 的解满足:1*x*,1/2()xHxF x= 其中，其中， 是由下述阈值函数所定义的对角非线性阈值是由下述阈值函数所定义的对角非线性阈值算子：算子：,1/2H,1/2,1/21,1/2( )(),()NHxhxhx=2/33,1/22( )22
33、54()1 cos() ,|3334 0 , iiixhxxOtherwise=+1/2L表表示示定定理理（Xu, et. al., L1/2 Regularization: A thresholding representation theory and a fast solver. IEEE TNNLS, 2012）.解的表示理论：解的表示理论：一个问题的的解是否具有解析表达形式？一个问题的的解是否具有解析表达形式？关于高维问题的研究关于高维问题的研究（L L1/21/2正正则化则化理论理论）对固定的 ，记 。则 问题的解 满足： 或 或 (0,1/)L*x*0ix =3*2/354()(
34、)4iBx l择一性直接推出择一性直接推出 问题的解之稀疏度问题的解之稀疏度 与正则化参数与正则化参数 的如下基本关系的如下基本关系: :3/23/2*1 969699kkBxBx+ 其中其中 表示向量表示向量 的第的第 个最大分量个最大分量l 问题的解是有限的问题的解是有限的 |kx|x1/2(ML)1/2(ML)kk定定理理( )( )BxxF x= 1/2(ML)Xu, et. al., L1/2 Regularization: A thresholding representation theory and a fast solver. IEEE TNNLS, 2012.解的择一性理论
35、：解的择一性理论：解的阈值截断性质，阈值等于多少？解的阈值截断性质，阈值等于多少？关于高维问题的研究关于高维问题的研究（L L1/21/2正正则化则化理论理论）RIP(Candes et al., 2005, 2006, 2007):02222max11kkxkAxx+Coherence (Donoho et al., 2001, 2003):122( )max,ijijjNiaaaAa =定理定理.对于任意的对于任意的 k- -稀疏信号稀疏信号x*：1)1) 若若 , , 则则(P(P1 1) ) 精确恢复精确恢复x*; ; (Candes & Tao, 2008) (Candes & Ta
36、o, 2008) 2)2) 若若 , , 则则(P(P1 1) ) 精确恢复精确恢复x*; ; (Li et al., 2011)(Li et al., 2011)3)3) 若若 , , 则则(P(P1 1) ) 精确恢复精确恢复x*; ; (Cai et al., 2012)(Cai et al., 2012)4)4) 若若 , , 则则(P(Pq q) ) 精确恢复精确恢复x*; ; (Wang et al., 2010) 5)5) 若若 , , 则则(P(P1 1) ) 精确恢复精确恢复x*; ; (Donoho & Elad, 2003)(Donoho & Elad, 2003)6)6
37、) 若若 , , 则则(P(P1 1/2/2) ) 有限步精确恢复有限步精确恢复x x* *; ; (Zeng et al., 2014) 20.414k20.4931k20.5k重构理论重构理论( )1/(21)Ak0.3333k重构理论：重构理论：在什么样的条件下通过松弛模型可完全重构原稀疏信号？在什么样的条件下通过松弛模型可完全重构原稀疏信号？( )0.295/Ak关于高维问题的研究关于高维问题的研究（L L1/21/2正正则化则化理论理论）RIP(Candes et al., 2005, 2006, 2007):02222max11kkxkAxx+Coherence (Donoho e
38、t al., 2001, 2003):122( )max,ijijjNiaaaAa =采样数理论：采样数理论：至少需要多少采样可保证完全重构原始稀疏信号？至少需要多少采样可保证完全重构原始稀疏信号？定理定理.假定信号维数为假定信号维数为N, ,则重建则重建k- -稀疏信号所需的测量数稀疏信号所需的测量数M满足：满足：1) 1) 对于确定性矩阵：对于确定性矩阵： ; ; (DeVore, 2007) (DeVore, 2007) 2)2) 对于高斯对于高斯 (Rademacher, (Rademacher, 亚高斯亚高斯) ) 随机矩阵随机矩阵: : ; ; (Baraniuk et al.,
39、2008)(Baraniuk et al., 2008)3)3) 对于对于Fourier (Hadamard) Fourier (Hadamard) 变换子矩阵：变换子矩阵： ; ; (Donoho & Tanner, 2009; Dossal, Peyre & Fadili, 2010) (Donoho & Tanner, 2009; Dossal, Peyre & Fadili, 2010) 2(log)O kMN=采样数理论采样数理论2log(/ )()kkN kOM=( log(/ )O kN kM =关于高维问题的研究关于高维问题的研究（L L1/21/2正正则化则化理论理论）l 将
40、通常的正则化参数选择问题（连续问题）划归到了稀疏度指定将通常的正则化参数选择问题（连续问题）划归到了稀疏度指定 问题（离散问题）。这一化简有重要意义。问题（离散问题）。这一化简有重要意义。l对于对于k k稀疏问题，给出了最优的正则化参数设置策略；然而很多稀疏问题，给出了最优的正则化参数设置策略；然而很多 学习问题本身就是一个学习问题本身就是一个k-k-稀疏问题。稀疏问题。 步骤1(求解k稀疏问题)：对于确定的稀疏度k，通过下述迭代过程求解问题的k -稀疏解： 步骤2(求问题的最优解)：将原问题 分解成若干个k-稀疏问题，重复步骤1 ；获得一组k-稀疏解，比较得出最优解。1,1/203/210(
41、) ,96|()|,(0,1/)9nnnnNnnnnkxHBxxRBxL +=1/2(ML)Half型型算算法法意义和价值意义和价值 关于高维问题的研究关于高维问题的研究（L L1/21/2正正则化则化理论理论）Half算法收敛性理论算法收敛性理论算法收敛性：算法收敛性：重构算法是否收敛？收敛到哪？有多快？重构算法是否收敛？收敛到哪？有多快？1)1)如果如果F -Lipschitz连续，连续， , ,则则 Half Half 型算法收敛型算法收敛; ;2)2)如果如果 ， 则则HalfHalf算法收敛到算法收敛到L L1/21/2的局部极小点；的局部极小点；3 3）在某些进一步条件下，）在某些
42、进一步条件下，HalfHalf算法的收敛算法的收敛 是最终线性的。是最终线性的。 -113/2min4(1)()TIIA Ab20040060080010001200140010-1510-1010-5100Number of Iteration nIteration Error (log-scale) |x(n)-x*|2(J.S. Zeng, S.B. Lin, Y. Wang, Z.B. Xu, L1/2 regularization: Convergence Analysis, IEEE TSP, 2014.)关于高维问题的研究关于高维问题的研究（L L1/21/2正正则化则化理论理论
43、） ：0 0，1 1元素矩阵，提取图像块中已知像素点；元素矩阵，提取图像块中已知像素点；：例子图像块集合：例子图像块集合图像填充：图像填充： 主要任务是通过数学模型和计算机算法，主要任务是通过数学模型和计算机算法，将图像中的缺失部分（由于污损、划痕、将图像中的缺失部分（由于污损、划痕、图像编辑、文字等造成的缺损）自动填图像编辑、文字等造成的缺损）自动填充完整充完整. .（Xu & Sun , IEEE TIP, 2010）稀疏正则化模型稀疏正则化模型 *= argmina|PnBnPYpn=1N|22+|a|1/21/2;Yp*=PYp+P(n*Bnn=1N)nBP关于高维问题的研究关于高维问
44、题的研究（应用举例应用举例）(a)蓝色区域为待填充区域；蓝色区域为待填充区域；(b) 填充完整图像填充完整图像(a)(b)(a)(b)关于高维问题的研究关于高维问题的研究（ L1/2理论应用到图像填充）理论应用到图像填充）视频监控问题视频监控问题: 从视频中提取背景与目标，以利于视频传输与目标分析。从视频中提取背景与目标，以利于视频传输与目标分析。+TransmissionReconstruction with B-T separation formCompressivemeasurements关于高维问题的研究关于高维问题的研究（ L1/2理论应用到视频监控）理论应用到视频监控）Model关
45、于高维问题的研究关于高维问题的研究（ L1/2理论应用到视频监控）理论应用到视频监控）l传统传统SAR成像过程：成像过程：l新的基于新的基于L1/2正则化理论的稀疏正则化理论的稀疏SAR成成像模型（像模型（ES-SAR）：原 始 回 波 信 号10020030040050060070080090010001002003004005006007008009001000二 维 SAR图 像501001502002503003504004505001002003004005006007008009001000雷达雷达观测观测HSAR成像成像S原原始始场场景景X二维成像二维成像X*()XS HxX=2
46、1/221/2minxxyxHlQ-+211/21/22min()XXYXSl-Q-+ES-SAR:CS-SAR:SNR(dB)Sampling rate(m/n) 010203040 10.80.60.40.20.020.040.060.080.10.120.140.160.180.2L1L1/2可重建区域可重建区域回波数据回波数据Y关于高维问题的研究关于高维问题的研究（L1/2理论应用到理论应用到SAR成像）成像）RDA新方法新方法RDARadarsat满采样数据成像结果满采样数据成像结果（场景大小（场景大小2048*2756）：）：完全与传统完全与传统SAR一样用于大场景成像，且有明显的
47、抑制旁瓣作用一样用于大场景成像，且有明显的抑制旁瓣作用 新方法新方法RDA： 4s原原CS方法：方法：2天天新方法：新方法： 415s关于高维问题的研究关于高维问题的研究（L1/2理论应用到理论应用到SAR成像）成像）实际数据验证实际数据验证距离多普勒算法距离多普勒算法50%采样下采样下ES-SAR成像成像关于高维问题的研究关于高维问题的研究（L1/2理论应用到理论应用到SAR成像）成像）港口盐田开展开展全球首次全球首次稀疏微波成像稀疏微波成像机载机载原理性系统验证实验；设计并原理性系统验证实验；设计并实现实现全球首部全球首部稀疏微波成像验证性原理样机。稀疏微波成像验证性原理样机。关于高维问题
48、的研究关于高维问题的研究（L1/2理论应用到理论应用到SAR成像）成像）机载平台（海南试飞）机载平台（海南试飞）70%采样下采样下ES-SAR成像成像70%采样下采样下ES-SAR成像成像关于高维问题的研究关于高维问题的研究（L1/2理论应用到理论应用到SAR成像）成像）关于大数据算法设计问题关于大数据算法设计问题 大数据算法设计问题大数据算法设计问题大数据算法：通过数据分解与变量分组实现计算过程的分解与组装，并可在分布式计算环境下实现、能支持大数据分析与处理的算法。l 大数据算法设计与分析方法学l 分布式计算的可行性理论l 流数据分析与处理算法l 分布数据（网络数据）高效处理算法l 超高复杂
49、性数据的分析、挖掘与学习l 大数据分析与挖掘基础算法热点问题热点问题：The Big Data Bootstrap. Kleiner et.al. 2012 ICML X X1 1X X2 2X X3 3X Xn n随机随机机制机制D1DkDm.聚合聚合机制机制l通过通过数据分解数据分解与与变量分组变量分组实现实现计算过程的分解与计算过程的分解与组装组装，并可在分布式计算环境下实现的算法，并可在分布式计算环境下实现的算法l能处理的数据集能处理的数据集具有大数据的典型特征之一具有大数据的典型特征之一：海：海量、异构、分布多源量、异构、分布多源 、流数据、超高维、高、流数据、超高维、高不确定性等不
50、确定性等l具有较低的复杂性具有较低的复杂性 ( (在大数据意义下：时间复杂在大数据意义下：时间复杂性性+ +存储复杂性存储复杂性+ +通讯复杂性通讯复杂性) ) l算法算法具有某些独特性质具有某些独特性质，如，如: :高度容错、解的可高度容错、解的可拼接可组装性等拼接可组装性等 大数据算法设计问题大数据算法设计问题(定义定义)BigDataData1Data2Data3Data4Data5Data m分解分解Map 1Map 2Map 3Map 4Map 5Map mShuffle，sortData1Data2Data k Reduce 1Reduce 2Reduce k组装组装数据数据模型模
