Maximal Sparsity with Deep Networks? Bo Xin1,2, Yizhou Wang1, Wen Gao1 and David Wipf2 各位老师， 朋友们，大家好。今天向大家介绍我们最近一个比较有意思的工作 Maximal Sparsity with Depp Networks (question mark)。 该篇工作是和我的PhD导师王亦洲老师，高文老师，还有我当时在微软亚洲研究院的mentor David Wipf老师合作的工作。 在这个工作中，我们试图把稀疏模型的求解和深度学习结合起来，探讨能否利用深度学习求解最稀疏编码这个NP难得问题，并从中讨论一些有意思的理论分析和实际设计。 1 Peking University 2 Microsoft Research, Beijing

Outline Background and motivation Unfolding iterative algorithms Theoretical analysis Practical designs and empirical supports Applications Discussion 我会首先介绍Maximal Sparsity的建模formulation和相关研究背景。 然后我将从迭代算法展开的角度建立稀疏求解和深度神经网络的联系。 之后我会motivate一下新颖的理论分析，也是我们工作的主要贡献之一。 然后，我会讨论一些具体的实际设计和实验结果，以及在该方法在光学立体问题中的一个应用。 最后，我会总结讨论一些想法。

Maximal Sparsity min 𝑥∈ 𝑅 𝑚 𝑥 0 𝑠.𝑡. 𝑦=Φ𝑥 Φ∈ 𝑅 𝑛×𝑚 𝑦∈ 𝑅 𝑛 ⋅ 0 # of non-zeros Maximal Sparsity 通常由下面这个formulation来描述。 其中Phi是一个已知的矩阵，通常被称为词典矩阵，y是一个观察向量，0范数表示一个向量中非零元素的个数，用来描述一个向量的稀疏性。 我们的目的是找到一个表示尽可能稀疏的表示 x，使 y = Phi x, 即 y 可以由词典Phi中的尽可能少的列（或者基）组合出来。 对这种稀疏性原则的研究最早可以追溯到13世纪著名的Occam‘s razor 法则; 而且在近代许多学科和我们熟知的智能领域得到了广泛的利用。

Maximal Sparsity is NP hard min 𝑥 𝑥 0 𝑠.𝑡. 𝑦=Φ𝑥 Combinatorial NP hard and close approximations are highly non convex 由于 0 范数的离散属性，这个问题属于组合优化问题，而且在一般意义上是NP难的问题。 对于它的连续优化近似也是会是一个充满local optimal的高度非凸的landscape。 所以大家常常采用一些近似目标函数或者算法试图在一定范围内求解该问题，比如大家可能比较熟悉的凸放松 l1 范数最小化方法，还有属于贪心的 orthogonal matching pursuit 方法，以及各种类型的迭代阈值算法，如 iterative hard thresholding IHT方法，这类算法相当于在每一次下降的过程中进行某种类型的可以引入稀疏性的阈值计算，从而最终实现稀疏求解。（事实上，l1最小化的问题常常也通过类似的迭代预制算法进行求解，比如 iterative soft thresholding ISTA，不过理论上 l1范数最小化是凸问题，其求解的准确性于具体算法无关。） Practical alternatives: ℓ 1 norm minimization orthogonal matching pursuit (OMP) Iterative hard thresholding (IHT)

Pros and Cons Numerous practical applications: Feature selection [Cotter and Rao 2001; Figueiredo, 2002] Outlier removal [Candes and Tao 2005; Ikehata et al. 2012] Compressive sensing [Donoho, 2006] Source localization [Baillet et al. 2001; Malioutov et al. 2005] Computer vision applications [John Wright et al 2009] 这些近似算法在很多机器学习和计算机视觉的很多问题中都取得了很不错的效果，比如 特征选择，Outlier removal，压缩感知，Source localization， 人脸识别等等视觉问题。 不过大部分这样的近似算法存在一个共同的缺点， 就是在词典矩阵Phi的Gram矩阵 Phi t Phi 具有较高的非对角线能量时，他们几乎很难准确求得稀疏解 x star。 Gram矩阵的非对角线能量反应了词典 Phi 中的相关性和结构信息。 Fundamental weakness: If the Gram matrix Φ T Φ has high off-diagonal energy Estimation of 𝑥 ∗ can be extremely poor

Restricted Isometry Property (RIP) A matrix Φ satisfies the RIP with constant 𝛿 𝑘 Φ <1 if Holds for all {𝑥: 𝑥 0 ≤𝑘}. (1− 𝛿 𝑘 Φ ) 𝑥 2 2 ≤ Φ𝑥 2 2 ≤ 1+ 𝛿 𝑘 Φ 𝑥 2 2 [Candès et al., 2006] 这种结构信息在稀疏的研究领域通常由一个叫做 RIP 常数的东西来描述 Restricted Isometry Property constant. 具体来说，对于一个词典 Phi ， 如果存在一个 常数 delta k Phi 使得所有 k-sparse 的 x 都满足这个方程，那么我们就称词典 Phi 关于常数 delta 满足 RIP 性质。 当然，这个常数主要是压缩感知领域为了一些理论的证明方便而设计的一个定义。它本质上是用来反映词典 Phi 的相关性大小的。如图所示的一个2维例子中，如果词典中的基 phi1和 phi2正交 如左图，那么该词典就具有较小的 RIP 常数， 反之， 如果 phi1 和 phi2 具有较强的相关性，如右图， 该词典的 RIP 常数就比较大。 所以 intuitively， RIP 常数较大的词典是比较困难的稀疏编码问题，常用算法不能够保证找到原始问题的最优解。 small RIP constant 𝛿 2 Φ large RIP constant 𝛿 2 Φ

Guaranteed Recovery with IHT Suppose there exists some 𝑥 ∗ such that Then the IHT iterations are guaranteed to converge to 𝑥 ∗ . 𝑦=Φ 𝑥 ∗ 𝑥 ∗ 0 ≤𝑘 𝛿 3𝑘 Φ <1/√32 我们拿 IHT （iterative hard thresholding）方法来举例，在 blumensath 和 Davies 2009 年的文章中，他们指出， 如果最优解 x star 满足 y= Phi x-star 而且 x star的非零个数小于等于 k 的情况下， 词典只有具有一个 delta_3k 小于 1/sqrt(32)的 RIP常数才能够保证 IHT 算法能够收敛到问题的最优解。 这样的要求大大限制了这些算法的求解范围，而且类似的 RIP 常数较小的约束在 l1 最小化等其他近似算法中也同样存在。 [Blumensath and Davies, 2009] Only very small degrees of correlation can be tolerated

Checkpoint Thus far What’s coming Maximal sparsity is NP hard Practical alternative suffers when the dictionary has high RIP constant What’s coming A deep learning base perspective Technical analysis 好，我们来checkpoint一下。 到目前为止我们介绍了maximal sparsity是NP难问题，已有的近似算法在词典具有较大 RIP 常数的时候不能够求得问题的最优解。 下面，我们介绍一个基于深度学习的视角来理解这些算法，并提出一套有意思的理论分析，这些分析将帮助我们figure out如何设计更好的稀疏求解方法。 其中为了方便，严谨的理论证明和分析，欢迎大家参考我们的文章，在这里我主要介绍这些理论背后的核心想法。

Iterative hard thresholding (IHT) Iterative soft thresholding (ISTA) Iterative algorithms Iterative hard thresholding (IHT) Iterative soft thresholding (ISTA) 𝑤ℎ𝑖𝑙𝑒 𝑛𝑜𝑡 𝑐𝑜𝑛𝑣𝑒𝑟𝑔𝑒, 𝑑𝑜 { 𝛻𝑥 ​ 𝑥= 𝑥 (𝑡) = Φ 𝑇 Φ 𝑥 (𝑡) − Φ 𝑇 𝑦 𝑧= 𝑥 (𝑡) −𝜇𝛻𝑥 ​ 𝑥= 𝑥 (𝑡) 我们首先来看一下两个常用的稀疏求解算法 IHT （迭代硬阈值算啊） 和 ISTA （迭代软阈值算法） 的迭代过程。 通常 我们在每一次迭代过程中 首先 计算当前位置的梯度，然后进行常规的梯度下降， 然后为了引入稀疏性，我们需要进行一次所谓的阈值投影过程。两个算法的区别在于，硬阈值投影保留绝对值最大的k个值， 将其他置为0，而软阈值方法 则 讲值将去 lambda， 做差后小于零的项置为0， 大于零的项保留其差后的值和正负号。 𝑥 (𝑡+1) =𝑡ℎ𝑟𝑠ℎ(𝑧) } 𝑥 𝑖 (𝑡+1) = 𝑧 𝑖 if | 𝑧 𝑖 | 𝑎𝑚𝑜𝑛𝑔 𝑘 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝑥 𝑖 (𝑡+1) = 𝑠𝑖𝑔𝑛 𝑧 𝑖 | 𝑧 𝑖 |−𝜆 𝑖𝑓 𝑧 𝑖 >𝜆 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Iterative hard thresholding (IHT) Iterative soft thresholding (ISTA) Iterative algorithms Iterative hard thresholding (IHT) Iterative soft thresholding (ISTA) 𝑤ℎ𝑖𝑙𝑒 𝑛𝑜𝑡 𝑐𝑜𝑛𝑣𝑒𝑟𝑔𝑒, 𝑑𝑜 { linear op 𝛻𝑥 ​ 𝑥= 𝑥 (𝑡) = Φ 𝑇 Φ 𝑥 (𝑡) − Φ 𝑇 𝑦 𝑧= 𝑥 (𝑡) −𝜇𝛻𝑥 ​ 𝑥= 𝑥 (𝑡) none linear op 如果我们把梯度下降部分 和 阈值投影部分分开来看，不难发现他们是一个 线性运算，后接一个非线性的算子。 𝑥 (𝑡+1) =𝑡ℎ𝑟𝑠ℎ(𝑧) } 𝑥 𝑖 (𝑡+1) = 𝑧 𝑖 if | 𝑧 𝑖 | 𝑎𝑚𝑜𝑛𝑔 𝑘 𝑙𝑎𝑟𝑔𝑒𝑠𝑡 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 𝑥 𝑖 (𝑡+1) = 𝑠𝑖𝑔𝑛 𝑧 𝑖 | 𝑧 𝑖 |−𝜆 𝑖𝑓 𝑧 𝑖 >𝜆 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

Deep Network = Unfolded Optimization? Basic DNN Template … linear filter nonlinearity/threshold Observation: Many common iterative algorithms follow the exact same script: 这使我们很容易想起 多层的神经网络。其中每层网络的输出 x t+1 通常由 输入 x t的线性变换 w xt + b 后接 非线性阶跃 f 变换得到。 所以，我们看到，前面分析的迭代稀疏算法follow了同样的规则， 那么我们可以认为迭代优化算法的展开一种特殊形式的深度神经网络。

Deep Network = Unfolded Optimization? Basic DNN Template … Fast sparse encoders: [Gregor and LeCun, 2010] [Wang et al. 2015] What’s more? 基于这样的connection，我们很自然地可以想到以可以设计一些由这些算法motivated的网络结构。 事实上，Gregor和LeCun 还有 Zhangyang Wang 最近的一些工作都成功设计了这些算法的对应网络，取得了快速的稀疏 encoder 并在许多应用中得到了promissing的结果。 不过到目前为止这方面的研究有两个重要的open quesiton。 第一，我们还并不知道，这样的基于学习得到的网络权重，能否比基于算法展开得到的网络 取得更好的稀疏求解效果。 另一方面，由前面的分析我们知道，这些算法本身的成功与否依赖于词典的低 RIP 属性，所以我们是否有机会通过学习得到能够处理 高 RIP 常数的词典稀疏编码问题。 在这两个方面，我们试图给出一些理论分析，并进一步挖掘出脱离具体算法的网络设计，实现更有效的稀疏求解方法。

Unfolded IHT Iterations … linear filter non-linearity 𝑊 = 𝐼 −𝜇 Φ 𝑇 Φ 𝑏 = 𝜇 Φ 𝑇 𝑦 为此，我们首先试图回答第一个问题： 对于一个稀疏算法展开的网络，学习到一个不同于算法设计的参数 W, b 是否更有优势。比如，在图中所示 IHT 算法的网络展开中，根据算法， W = I – mu Phi t Phi b = mu Phi T y. 那么这样的 W 和 b的取值是不是最优的呢？ Question 1: So is there an advantage to learning the weights?

Effects of Correlation Structure Low Correlation: Easy High Correlation: Hard 为了评价这种优劣， 我们首先 recall 一下， IHT 算法在 词典 具有 RIP 常数 delta-3k < 1/ sqrt(32) 的时候可以成功求解原始问题。 我们知道，如果词典中的元素随机 iid 采样， 词典具有很小的相关性，具有满足条件的 RIP 常数。 不过更多时候，实际的词典具有结果，比如，如果我们再这个 满足 RIP 常数 的 Phi –uncor 的基础上随便加上一个 低秩 的成分 Delta, 那么它的 RIP 常数通常就远远超过 1/sqrt(32) 了， 如右图所示。 small RIP constant large RIP constant low rank

Performance Bound with Learned Layer Weights Theorem 1 There will always exist layer weights 𝑊 and bias 𝑏 such that the effective RIP constant is reduced via where Ψ is arbitrary and D is diagonal. 𝛿 3𝑘 ∗ Φ = inf Ψ 𝐷 𝛿 3𝑘 ∗ ΨΦ𝐷 ≤ 𝛿 3𝑘 [Φ] effective RIP constant original RIP constant 面对这样的情况，我们提出，总是存在不同于IHT算法所对应的 W 和 b 的取值，能够降低一个 so called effective Rip 常数。 所谓 实际 RIP 常数， effective RIP 主要指我们可以通过对原始词典进行左右乘的变换，从而将问题投影到一些不同的空间，使得在这个空间的相应稀疏求解实际上处理一个更为理想的 RIP 常数 的词典。 证明通过分析算法收敛点的不定点特性完成。 所以，总结一下，It is possible to reduce high RIP constants [Xin et al. 2016] It is therefore possible to reduce high RIP constants

Practical Consequences Theorem 2 Suppose we have correlated dictionary formed via With Φ 𝑢𝑛𝑐𝑜𝑟  iid 𝑁(0,𝜈) entries and Δ sufficiently low rank. Then Φ (𝑐𝑜𝑟) = Φ 𝑢𝑛𝑐𝑜𝑟 +Δ large RIP small RIP 我们来具体考虑这个具有低秩成分的词典特例。即 Phi-uncor 从 iid 取得， Phi-cor 增加了低秩成分 Delta 在这种情况下 我们可以证明， 存在合适的权重能够通过向低秩成分的 0 空间进行投影 来实现 effective RIP常数约等于这个非低秩成分的 RIP 常数， 从而大大的降低了 实际 的 RIP 常数。 当然，为了完整性，我们需要并证明了在投影空间的实际稀疏问题的收敛和原始空间问题的收敛是对应的。 所以，we can actually somehow undo low rank correlation that wound otherwise produce a high RIP constant [Xin et al. 2016] So we can ‘undo’ low rank correlations that would otherwise produce a high RIP constant …

Advantages of Independent Layer Weights (and Activations) Theorem 3 … With independent weights on each layer Often possible to obtain nearly ideal RIP constant even when full rank D is present 前两个 Theorem 的分析告诉我们 即使在每层网络参数固定的情况下，学习得到的 w 和 b 是能够比算法得到的 w 和 b 取得更好的稀疏求解的。 很自然，我们要问自己第二个问题。Do independent weights help even more? 事实上，通过explore similar ideas， 我们可以更进一步证明， 如果我们采用每一层独立的权重举证 W 和 b 或者可变的非线性层， 我们可以在更加困难和一般的情况下 恢复一个 几乎 理想的 RIP 常数 [Xin et al. 2016] Question 2: Do independent weights (and activations) has the potential to do even better? Yes

Advantages of Independent Layer Weights (and Activations) Φ=[ Φ 1 ,… Φ 𝑐 ] Φ 𝑖 = Φ 𝑖 𝑢𝑛𝑐𝑜𝑟 + Δ i 𝑥 (𝑡+1) = 𝐻 ( Ω 𝑜𝑛 𝑡 , Ω 𝑜𝑓𝑓 (𝑡) ) [ 𝑊 𝑡 𝑥 𝑡 + 𝑏 𝑡 ] 这里，我来举一个相关的例子。 假设我们的词典 Phi 现在由 Phi1..Phic 组成，其中每一个成分都具有自己的低秩和噪声部分。那么我们相当于具有了一个满秩而且 RIP 常数很大的词典。 事实上，这个词典具有一个两层的层级结构。每个Phi I 相当于一个cluster, 在cluster 直接的区分是一个层面的问题，在cluster内部的区分是一个更细粒度的问题。 所以 intuitively 我们可以通过利用不同网络层之间不同的 w 和 b 以及非线性变换部分来实现不同层网络 处理 不同粒度 的稀疏问题。 比如第一层网络主要用来处理 cluster 级的选择

Advantages of Independent Layer Weights (and Activations) Φ=[ Φ 1 ,… Φ 𝑐 ] Φ 𝑖 = Φ 𝑖 𝑢𝑛𝑐𝑜𝑟 + Δ i 𝑥 (𝑡+1) = 𝐻 ( Ω 𝑜𝑛 𝑡 , Ω 𝑜𝑓𝑓 (𝑡) ) [ 𝑊 𝑡 𝑥 𝑡 + 𝑏 𝑡 ]

Advantages of Independent Layer Weights (and Activations) Φ=[ Φ 1 ,… Φ 𝑐 ] Φ 𝑖 = Φ 𝑖 𝑢𝑛𝑐𝑜𝑟 + Δ i 𝑥 (𝑡+1) = 𝐻 ( Ω 𝑜𝑛 𝑡 , Ω 𝑜𝑓𝑓 (𝑡) ) [ 𝑊 𝑡 𝑥 𝑡 + 𝑏 𝑡 ]

Advantages of Independent Layer Weights (and Activations) Φ=[ Φ 1 ,… Φ 𝑐 ] Φ 𝑖 = Φ 𝑖 𝑢𝑛𝑐𝑜𝑟 + Δ i 𝑥 (𝑡+1) = 𝐻 ( Ω 𝑜𝑛 𝑡 , Ω 𝑜𝑓𝑓 (𝑡) ) [ 𝑊 𝑡 𝑥 𝑡 + 𝑏 𝑡 ] 而第二层则主要 负责 分析 cluster 内部的稀疏选择。一个简单的 gating 机制就可能让我们记住第一层的选择，从而在第二层把重点放在被选中的策略特然内部。 通过这个例子，不难理解，采用independent weights 可以potentially 更进一步帮助我们求解更难的稀疏问题。

Checkpoint Thus far What’s coming Idealized deep network weights exist that improve RIP constants. Thus far What’s coming Practical design to facilitate success Empirical results Applications 好，在做一次 checkpoint 到目前为止，我们知道， 存在理想的网络权重设置，能够在很大程度上降低 effective RIP 常数，从而更好的求解原始问题。 在这里需要说明一下： 对于具体的问题，我们几乎无法得知词典的具体结构性，所以我们无法 通过 hand craft 的方式设计出相应的网络来实现最优的 effective RIP常数。但这似乎正是基于学习的方法的好处所在。类似于利用 CNN 代替 hand craft feature SIFT一样，我们相信对于这样的不确定性，学习得到的权重设置将 implicitly 优于大部分 hand craft的参数设置，包括各种传统迭代算法的对应权重。 下面我介绍一些具体的design trick和实验结果。

Alternative Learning-Based Strategy Treat as a multi-label DNN classification problem to estimate support of 𝑥 ∗ . The main challenge is estimating supp[x] Once support is obtained, computing actual value is trivial ℎ 𝑦−Φ𝑥 2 based loss will be unaware and expend undue effort to match coefficient magnitudes. Specifically, we learn to find supp[x] using multilabel softmax loss layer 首先我们提出 通过把问题转化为一个多label 分类问题进行求解。主要的想法是： 1 对于Maximal sparsity这种稀疏问题，我们发现其中最challenge 的部分是估计目标向量的support 2 一旦这个support被准确的求得，规矩目标向量 x-star的值可以通过简单的least square得到。 3 但是目前领域中常用的给予 y-Phi x 2范数的loss项的方法是没有办法明确利用这种信息的，它们可能会导致网络的学习过程 spend undue effort去直接match value，而不是focus在support上 4 事实上，如果大家去想一下目前的分类问题，在一张图中如果既有 人，也有自行车，该图的label 可能也既有人也有自行车，但是 there is no way to guarantee 两个label的贡献一定是一致的。所以，多目标分类本身是可以用来鲁棒的进行这种没有权重的分类问题的。 最后，这种多label分类 我们直接采用一个multilabel的 softmax就能够完成，和single label softmax 主要的区别在于向后传播的时候同时有多股梯度信息从几个label对应的位置流出。

Alternative Learning-Based Strategy Adopt highway and gating mechanisms Relatively deep nets for challenging problems  such designs help with information flow Our analysis show such designes seem natural for challenging multi-scales sparse estimation problems The philosophies of generating training sets. Generative perspective 𝑥 ∗  𝑦=Φ𝑥 ∗ Not 𝑦  𝑥 ∗ =𝑜𝑝𝑡𝑖𝑚𝑖𝑧𝑎𝑖𝑡𝑜𝑛(𝑦) Unsupervised training 𝑥 ∗ are randomly generated 另外，在刚才的理论分析部分，我们注意到一个有意思的gating机制可能帮助我们更好的处理复杂的层次化的稀疏求解问题。在某种意义上，我们argue 几乎所有困难的稀疏问题都是在某种程度上多个尺度的稀疏问题交织在一起导致的。所以，intuitively 某种形式的highway和long term memory应该会更有利于求解这种问题。 另一方方面，我们发现先 IHT ISTA等常用的算法，在碰到 RIP 较高的困难的稀疏问题的时候，通常要进行很多次的迭代才能够收敛。所以，我们需要采用比较多层的，或者说足够深的神经网络能够更好的帮助问题求解。在这方面，像highway 和 lstm这样的跨层练级，更有利于information flow， 从而更利于训练。 最后，我们来考虑如何产生训练样本。 通常，对于这样稀疏网络的学习，比如基于 IHT 的网络和基于 ISTA 的网络。大家都是随机的产生或者从一些辅助数据中产生很多 y， 然后通过具体算法 计算得到 相应的 x-star ，之后采用 y输入，xlabel的方式训练。 但是由于我们的目标是求解maximal sparsity的np问题， 而且我们知道已有算法常常是faulty的，所以我们不能够在given y的时候得到真正的x-star ，所以这样产生的label x进行训练将几乎必然导致错误。 相反，我们提出直接随机的产生 x-star 然后又 x-star generatively 得到 y=Phi x-star。 除了能够保证这样产生的 x y 对是正确的match意外，这样做得好处是我们可以产生几乎无穷多的训练样本，而且不需要产生label。在某种程度上属于无监督的自我训练， almost labeling effort free。 我们price是，我们无法保证训练时采用的x-star的分布很难和test时间真正问题 x-star的分布相一致，不过我们的实验表明，对于稀疏求解这个问题，我们的模型对于训练数据 x 采样的实际分布变化是足够鲁棒，后面我们会具体讨论。

Experiments We generate Φ= 𝑖 1 𝑖 2 𝑢 𝑖 𝑣 𝑖 𝑇 where 𝑢 𝑖 , 𝑣 𝑖 are iid 𝑁(0,1) Super-linear decaying singular values With structure but quite general Values of 𝑥 ∗ 𝑈-distribution : drawn from 𝑈 −0.5,0.5 excluding 𝑈[−0.1,0.1] 𝑁-distribution : drawn from 𝑁 +0.3,0.1 𝑎𝑛𝑑 𝑁(−0.3,0.1) Experiments Basic: U2U Cross: U2N, N2U 我们来设计一个模拟实验，其中首先产生一个有机构的词典 Phi。 （这样做保证了词典具有super-linear decaying的singular value， 同时又不太拘泥于任何具体的结构形式。） 然后，我们通过两种先验分布来产生 x-star。 即 U 分布 和 N 分布 。。。 我们把利用 U 分布产生训练样本， 同样利用 U 分布产生测试样本的实验成为基础实验 U2U, 相应的U2 N 和 N2U是训练和测试不同的cross实验

Results Strong estimation accuracy Robust to training distributions 左图是我们在 基础 U2U上对比我们的方法 和 已有方法的结果。。其中我们分别采用了基于residual 和 lstm的网络，如图中的紫线和红线。 我们对比了IHT 和 ISTA算法，已经基于他们的神经网络，可以看出，我们的方法明显超过了这些传统方法结果。 另外，如右图所示可见， 我们的方法在训练和测试分布不一样的时候，表示几乎非常consistent。这一点对于我们这种随机设计x-star的方式是非常重要的。 Strong estimation accuracy Robust to training distributions Question 3: Does deep learning really learn ideal weights as analyzed? Hard to say, but it DOES achieve strong empirical performance for maximal sparsity

Robust Surface Normal Estimation Input: Per-pixel model: Can apply any sparse learning method to obtain outliers … Specular reflections, shadows, etc. (outliers) observations under different lightings 最后，来看一个实际应用。 我们考虑一个光学立体的问题。 具体来说，我们希望利用在不同光照条件下产生的一组图片，来回复原始物体的3D信息，即物体上每个点的normal 法线方向。 在Ikehata 2012年的工作中，这个问题可以被建模成 per pixel的稀疏求解问题。即每个点在不同光照情况下的观察向量 y = lighting matrix L 乘以 真是法线方向 加上 一个稀疏的噪声，其中噪声主要是有高光或者阴影产生的。 lighting matrix raw unknown surface normal [Ikehata et al., 2012]

Convert to Sparse Estimation Problem 这样一来，如果我们进一步把问题的左右两边分别投影到光场矩阵的0空间，即左成一个投影向量。 我们可以得到如下所示的标准的稀疏问题。这样一来我们便可以利用前面讨论的方法来取代传统的稀疏算法进行求解。有意思的是，我们再产生训练样本的时候仅仅采用一个均值和方差可调的高斯分布就能够训练一个足够好的稀疏估计模型。 # of nonzero elements Once outliers are known, can estimate n via: [Candès and Tao, 2004]

Real time photometric stereo 在上图中，我们展示了我们的方法和传统的算法在恢复这个bunny image normal的误差图。可以看出我们的方法具有最小的误差。而且一旦完成学习，每个像素点的估计在测试阶段仅仅是一次向前传播计算。比传统的算法的时间效率要高出50到100倍左右。

Conclusions First rigorous analysis of how unfolded iterative algorithms can be provably enhanced by learning. Detailed characterization of how different architecture choices affect performance. Narrow benefit: First ultra-fast method for obtaining optimal sparse representations with correlated designs (i.e., high RIP constants). Broad benefit: General insights into why DNNs can outperform hand-crafted algorithms. 最后，简单总结一下。

Thank you!

Network structure Residual LSTM