Epipolar a personal journal

最小二乘问题(十五)

对于线性最小二乘问题 $\min\|Ax-b\|^2$ ,我们知道它的最优解同时是标准方程 $A^TAx = A^Tb$ 的解。

如果设 $M = A^TA$ ,在 $A$ 列满秩时,$M$ 是对称正定矩阵。我们知道,存在唯一的下三角矩阵 $L$ ,在对角元大于零的前提下满足 $LL^T = M$ 。这被称为矩阵 $M$ 的 Cholesky 分解。

与此同时,如果我们对 $A$ 进行 QR 分解,同样存在唯一的 $QR=A$ 满足 $R$ 的对角元大于零。将后者代入 $M=A^TA$ ,便可发现 $R^TR = R^TQ^TQR = A^TA = M = LL^T$ 。这意味着:矩阵 $A$ 的 QR 分解对应着矩阵 $M$ 的 Cholesky 分解。

回到最开始的线性最小二乘问题,若 $QR = A$ ,对原始问题的余项进行正交投影变换得到如下的新问题:

它的标准方程是 $R^TRx=R^TQ^Tb$,也就恰好是 $A^TAx=A^Tb$ 。这也就是说这个新问题具有与原问题相同的最优解。

前面的一系列分析基于了 $A$ 列满秩的假设,在 $A$ 的行数小于列数时,这是不成立的。但抛开矩阵分解结果唯一性,上面的 QR 分解与 Cholesky 分解的类推关系依旧成立。这意味着我们依旧可以用这种正交投影的方式来得到与原始问题具有相同解的新问题。

The Busy Indicator

当手机从一天不充没问题变成每天两充还不够的时候,不是手机电池不行了,是接近年底了真的很忙啊……

“阈值”优化

有时我们想求一系列数值 $f_1, f_2, \dots, f_n$ 中绝对值大于 $\lambda$ 的部分,如何非常有逼格地做这件事儿呢?

有趣的是,下面的优化解答了这一问题,其中 $f=(f_1, f_2, \dots, f_n)^T$ 是这些数值构成的列向量:

求解令上面问题最优的 $x$ ,则 $x$ 中非零项所在的维度便对应了想要的 $f_i$ 所在的维度。更具体地说,$x_i = \mathrm{sgn}(f_i)\cdot\max(|f_i|-\lambda, 0)$ 。这个操作等于将 $f$ 的所有元素向零方向收缩 $\lambda$,因此得名 shrinkage 。

从这个看似简单的优化,可以扩展出很多复杂的数学工具,包括著名的 LASSO 和 SVT 算法。

装作自己是 bat 批处理的 lua 脚本

最近需要一些管理用到的程序包的工具,无奈在 Windows 下使用批处理(bat)脚本编写这些实在太麻烦了,于是便研究如何使用更友好的脚本语言。Lua 是一个轻量的程序语言,并且根据需要进行扩展,非常符合我的一些特殊使用需求,因此我便尝试用 Lua 编写管理脚本。但是,要想方便地用 .lua 扩展名脚本直接运行,还需要为系统关联扩展名到 Lua 解释器,这就导致脚本在其它机器上使用略有不便。

好在,为了解决这一问题,可以简单地写一个 script.bat 脚本,里面的内容也很简单:

lua.exe script.lua %*

这么一来,通过执行 script.bat args... 就可以得到执行 script.lua args 同样的效果。但是,这样一来,每次就需要一个 lua.exe 和两个脚本,于是便思考如何将 lua 脚本直接嵌入在 bat 文件中。

沿着这一思路,首先想到的是将脚本以字符串方式放在 bat 中,每次执行的时候写入到临时文件,然后用 lua.exe 调用。但是这么做显得不够优雅,这个临时文件的回收也比较麻烦。经过一些思考,我得到了下面的方法,可以直接在 bat 中编写 lua 脚本。并且有趣的是,这种脚本既是一个 bat 脚本,也是一个 lua 脚本。这就意味着,我们可以直接执行 script.bat ,也可以用 lua.exe script.bat 执行它,得到同样的效果。

要想这么做,只要在需要执行的 lua 脚本前面加上下面的头部就可以了:

rem = nil --[[
@echo off
lua.exe %0 %*
exit /b --]]

它的原理比较巧妙:第一行的 rem 恰好是批处理中的注释命令,因此这一行后面的所有内容都被批处理视为注释。第二行到第四行实际执行了批处理命令,其中第三行将当前的脚本重新交给 lua.exe 运行,并将全部的命令行参数原封不动传递,第四行的 exit 退出了批处理。由于批处理是按行解释执行,在 exit 之后的内容也就再也不会被批处理载入,不会引起任何的错误。

而从 lua.exe 看来,第一行将 rem 变量赋值为了空值,也就是什么事情都没有做,此后到第4行为止的内容全部是 Lua 中的块注释,因此直接被忽略,于是 lua.exe 便会将第四行之后的一切内容视作正常的 Lua 脚本执行。

搬家完成

至此,我从 https://epipolar.tumblr.com/ 到这里的搬家就告一段落了。过程真的是无比漫长和艰辛。

为什么搬家

之所以想到要搬家,是有几方面的原因的:

  • Tumblr 常年被墙,为我写文和浏览都带来了障碍,虽然 ghpages 也偶尔会被照顾,相比之下还是比 Tumblr 友好的。
  • Tumblr 的功能比较局限,特别是我的文章偶尔会用到代码,此前只能用引用块儿将就。虽说实现代码高亮的方式也有,但还是比较绕弯。
  • Tumblr 文章的地址采用了一个 ID ,很不直观。相较之下 ghpages 中就可以用比较友好的 permalink 。
  • 在 Tumblr 上使用自定义的 assets 比较繁琐。我在利用 P5.js 制作一些内容时深深地感受到了不便。
  • Tumblr 自带的 Archive 采用的是块状的布局,这就使得按标题找文章非常得不方便。如果图像内容居多,采用 Tumblr 就更加合适了。
  • Tumblr 上一些“另类”内容太多,具体是什么大家心里有数。

因此,在朋友阅读我的 Tumblr 文章时发出了对索引不便的感叹后,我就决定搬家了。

搬家的过程

如一开始所说,整个过程充满了艰辛。对于 ghpages/jekyll/static site 这些,我几乎都很陌生,可以说从零开始。因此一切都在摸索和试错中进行。

事实上,可以搭建本地的 jekyll (或者 hexos,听说是个更加易用的平台),在本地将页面输出好然后只把最终的静态页面 push 到 ghpages 上。这样,各种事情都可以在本地调试好。

但我最终没选择这么做,而是采用了最简单粗暴的提交到 ghpages 然后浏览的方式。一方面是懒,另一方面是如果在本地搭建 jekyll 环境,还要再接触 Ruby ,这又是个相对陌生的事物。此外,我终归是在 Windows 上工作居多,在 Windows 上搭建 Ruby/jekyll 环境又会带来额外的复杂性……

为了减少工作量,我尝试了利用 Tumblr 官方的 API 自动抓取全部文章和文章中的图片。但由于 Tumblr 文章采用了 HTML 编码,我基本只保留了抓取到的文章元信息,例如标题、时间、标签。文章内容则是复制粘贴后利用 Markdown 重排。期初尝试的是 Node.js 的 API ,却发现 Node.js 不支持全局代理,后改用了 Python 。Node.js 也算是初次尝试,不过总地来说,在 Windows 下尝试使用任何脚本语言都会伴随着痛苦。

ghpages 采用的是 jekyll+kramdown 。kramdown 自称支持 MathJax ,但实际上还是要在模板上做很多的工作。在 Tumblr 中书写公式时,为了避免 Tumblr 自作聪明的各种转换,需要额外 escape 一些字符。到了 kramdown 中,同样要做类似的事情,而两边需要做的又不相同,这就意味着所有数学文章要经过一番转换……这一过程,我基本采用了人工操作,以保证质量。另外,代码块也要从 Tumblr 里的引用改成正经的高亮块,也是一番工作。图片通过自动抓取实现了本地导出,可是图片的名字都是一塌糊涂。因此在文章里插入图片时就要重新把图像名字美化,又是很大一块的开销。

模板方面,采用了 Hyde 。在它的基础上进行了一些修改以适应我的需要。例如加入了 Disqus 评论,Post 列表,Tag 列表,删除了一些无用的元素,为 MathJax 加入了自动重排版的功能。一些可直接套用内容的 Post 模板正在设计中,应该今后会加入。此外目前模板上对 Hyde 的版权还没有标注出来,也是因为懒,很快会修正。

搬家之后

虽说是搬家,并不意味着旧的 Blog 就完全放弃了,在今后一段时间里两边会平行地使用。不过内容上会出现一些区分:

  • ghpages 会更侧重原创文章以及各种非文章形式的页面
  • Tumblr 上会更侧重一些有趣内容的转载,同时同步更新部分 ghpages 上的文章。

在目前的搬家中,我已经忽略了一些 Tumblr 上的转载文章内容。在 Tumblr 内发现的,就留在那里不要搬过来了。

此外,部分文章在搬运时也重温了内容,进行了细微的修改,添加了一些后记来补充撰写文章后的新认知。这些在 Tumblr 一侧不会再更新了。

总而言之,这里将会是以后我记录和分享自己学到的知识的场所。风格上,还会一直坚持走浅显易懂的路线。利用 ghpages 的灵活性,今后还会尝试加入各种有趣的内容,还请多多关注。


发在这边的文章,一些文章的 permalink 中藏了一些微妙的 puns ,算是一些小彩蛋,这也是在 Tumblr 发文无法享受的乐趣 :)