**原文出自：压缩感知中的数学知识：凸优化**，简单易懂。
这里再推荐一个关于凸优化的综述Convex Optimization Overview，介绍的比较全面。
对于任意两点x和y(x,y ∈ Rn)，则对于0<=μ<=1，关系μx+(1-μ)y表示x和y连线之间的所有点。把n简化到一维的情况，即x和y就是两个实数。证明如下：
1 | 假设y>x(即y-x>0)，在一维情况下，只要证明x<=μx+(1-μ)y<=y就可以了。 |
虽然上面证的只是一维，但在多维时可以分解，比如二维时可以分解成横坐标x和纵坐标y，对于每一个坐标轴都是一维的，综合起来就得到了多维的结果。对应到几何关系上来看，对于0<=μ<=1，关系μx+(1-μ)y表示x和y连线之间的所有点。
明白了上面的基础后，这个定义就简单了：若某集合中的x和y两个点，若x和y连线之间的所有点（即0<=μ<=1，μx+(1-μ)y）仍属于这个集合，则称此集合为凸集。
直观几何表示如下：
左边的是凸集，右边的不是凸集，因为右边的集合中任意两点x和y连线之间的所有点有时不属于这个集合（右图中的连线）。
压缩感知理论指出：只要信号是可压缩的或在某个变换域是稀疏的，那么就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量的投影中以高概率重构出原信号，可以证明这样的投影包含了重构信号的足够信息。
这里分享一个Rice University关于压缩感知的资料集，以下
The dogma of signal processing maintains that a signal must be sampled at a rate at least twice its highest frequency in order to be represented without error. However, in practice, we often compress the data soon after sensing, trading off signal representation complexity (bits) for some error (consider JPEG image compression in digital cameras, for example). Clearly, this is wasteful of valuable sensing resources. Over the past few years, a new theory of “compressive sensing” has begun to emerge, in which the signal is sampled (and simultaneously compressed) at a greatly reduced rate.
As the compressive sensing research community continues to expand rapidly, it behooves us to heed Shannon’s advice.
Compressive sensing is also referred to in the literature by the terms: compressed sensing, compressive sampling, and sketching/heavy-hitters. ->完整内容
你眼中看似落叶纷飞变化无常的世界，实际只是躺在上帝怀中一份早已谱好的乐章。
双调排序是data-independent的排序， 即比较顺序与数据无关的排序方法， 特别适合做并行计算，例如用GPU、fpga来计算。
1、双调序列
双调序列是一个先单调递增后单调递减（或者先单调递减后单调递增）的序列。
2、Batcher定理
将任意一个长为2n的双调序列A分为等长的两半X和Y，将X中的元素与Y中的元素一一按原序比较，即a[i]与a[i+n] (i < n)比较，将较大者放入MAX序列，较小者放入MIN序列。则得到的MAX和MIN序列仍然是双调序列，并且MAX序列中的任意一个元素不小于MIN序列中的任意一个元素。
1 | for (i=0;i<n;i++) { |
3、双调排序
假设我们有一个双调序列，则我们根据Batcher定理，将该序列划分成2个双调序列，然后继续对每个双调序列递归划分，得到更短的双调序列，直到得到的子序列长度为1为止。这时的输出序列按单调递增顺序排列。类似于归并排序。
见下图，升序排序，具体方法是，把一个序列(1…n)对半分，假设n=2^k，然后1和n/2+1比较，小的放上，接下来2和n/2+2比较，小的放上，以此类推；然后看成两个(n/2)长度的序列，因为他们都是双调序列，所以可以重复上面的过程；总共重复k轮，即最后一轮已经是长度是2的序列比较了，就可得到最终的排序结果。
FMCW全拼Frequency Modulated Continuous Wave，这周看的MOBICOM2016关于声信号（Acoustic Signal）跟踪手势的几篇论文中提到的一个比较重要的声波测距技术。
FMCW技术和脉冲雷达技术是两种在高精度雷达测距中使用的技术。其基本原理为，发射波为高频连续波，其频率随时间按照三角波规律变化。雷达接收的回波的频率与发射的频率变化规律相同，都是三角波规律，只是有一个时间差，利用这个微小的时间差可计算出目标距离。
我们来通过MOBICOM2016的一篇论文 CAT: High-Precision Acoustic Motion Tracking 学习一下FMCW技术的测距原理，下图摘自该篇论文。
我的大三生涯就此落下帷幕，结局没有让我失望。
在刚升大三的时候，我是抱着和LY同学一起考研的心态，兴致勃勃地规划复习计划，还买了一个考研复习本子，掏出了尘封已久的线性代数开始复习，背单词等等。在拖拖拉拉的复习了小半学期，确实看完了线代，但是感觉迟迟没有状态。
在大三上后半学期，也就是大概去年11月份的时候，我们决定参加信息安全大赛，拼一下加分。当时还是抱着比赛与考研并行的心态，信誓旦旦的说寒假回家复习微积分2333，自然这个计划没有实现。好在，我们信安大赛找到了一个很好的指导老师，督促我们的进度。从12月开始，我们就各种查找资料，定作品主题，看论文，翻网页，确定主题差不多持续了一个多月，也是机缘巧合吧，我们选择了区块链这个方向，也就有了我们的作品：论文区块链DCI管控系统，运用区块链做论文版权保护。主题确定之后，我们就开始着手写作品的文档，确定作品的架构和需求才好开始编码。怎么说呢，信安大赛的作品赛我觉得就是一个以文档为主体的比赛，虽然编码也很重要，因为决赛还是要演示的，但是写好文档真的很重要，这里给大家看下我们的文档迭代版本有多么的多！
原文链接：MPI newbie: What is “operating system bypass”?
顺便提一下标题那个有意思的词newbie，念成牛逼，实际上是新手的意思哈哈！OS bypass译为系统旁路。
转载请注明出处，正文开始
“OS bypass”这个术语经常会在MPI和HPC的对话中被提及，它通常被认为在许多MPI的应用中是“必备品”，因为它能提高应用的性能。
但是，它到底是什么呢？如果它对提高应用性能有帮助，那么为什么不所有应用都使用OS bypass呢？
通常访问网络硬件，比如访问Network Internet Cards[what is NICs]的模式，就是先调用用户空间的API，例如TCP socket调用包括bind、connect、accept、read、write等，然后交给操作系统，由操作系统来调用懂得如何与当前电脑中的NIC硬件交互的设备驱动。
这种模式已经被很好的验证过了，而且几乎是所有应用程序（除了HPC）的工作方式。
那么HPC应用为什么不使用这种模式呢，至少有两大原因：
今天看了一篇关于虚拟网络拥塞控制的paper，核心思想就是把新的拥塞控制算法通过虚拟机管理程序将其翻译为旧的描述方式，以便于那些传统的、不能更新的应用也可以使用新的算法，Virtualized Congestion Control(SIGCOMM2016)。里面提到了三种网络拥塞控制算法：TCP with ECN，DCTCP，TIMELY。在这里分享几篇博文学习一下。
其中涉及到一个TCP incast概念：TCP incast是指在数据中心网络中，随着同时参与数据传输的服务器数据增加，产生的数据流量会将瓶颈交换机的缓冲区溢出，引起丢包事件以及随后的数据重传，最终导致系统吞吐量急剧下降。
这周看到了SIGCOMM2016上的一篇论文Globally Synchronized Time via Datacenter Networks，文中提出了一个新型的DTP时钟同步机制，提高全网时钟同步的精确度。本文主要介绍下在abstract中提到了NTP和PTP两种现行的时钟同步协议。
在现代通信网络中，大多数电信业务的正常运行要求全网设备之间的频率或时间差异保持在合理的误差水平内，即网络时钟同步。网络时钟同步包括相位同步和频率同步两个概念。
相位同步（Phase synchronization），也称为时间同步，是指信号之间的频率和相位都保持一致，即信号之间相位差恒定为零。
频率同步（Frequency synchronization），是指信号之间的频率或相位上保持某种严格的特定关系，信号在其相对应的有效瞬间以同一速率出现，以维持通信网络中所有的设备以相同的速率运行，即信号之间保持恒定相位差。
为防止概念混淆，下文中时间同步统一表示相位同步，时钟同步表示同时进行相位同步和频率同步。