Eckart–Young theorem (低维矩阵近似)

       Eckart–Young theorem讲的是有一个矩阵M,找到另一个rank为r(小于M的rank)的矩阵N,使得\sum\limits_i\sum\limits_j (M_{i,j}-N_{i,j})^2 最小。其实是Frobenius norm

      解法是对M进行SVD后得M=U\sum V^*,取前r个最大的特征值和对应的特征向量,即:N = U\sum_r V^*。为何这样做之后|| M -N ||_F最小,可以见课堂笔记。主要是使用了Lagrange Multiplier。以下为实例代码。

      使用Octave计算后,可得如下结果示意图,可见,误差很小。代码见github。图中绿色为结果,蓝色为原始点。

EckartYoung

       后来作业里有一个要求,1_n^T*N = 0,即满足N列均值为0。条件强了很多,所以结果就不好了。图中绿色为结果,蓝色为原始点。

hw

 

参考资料:

  1. SVD
  2. Moreau Envelopes

 

[第3天]32位模式和c语言

       终于到了第3天,这次作者太坑。搞的我差点放弃。这次是真的一天,一整天,拼起来24小时。今天我也终于实现了第一个内核,不再是简单的引导了。而且也进入CPU保护模式,这个就吊了。我还要吐槽下,为何其他很多中文博客TMD都是直接复制粘帖代码?坑啊。

IPL:

       IPL(Initial Program Load),就是把系统导入内存然后跳入系统的入口。跟Booting是一个意思我才知道。这个阶段BIOS读入磁盘上的第一个扇区,一共512Bytes。在这个阶段,就是所谓的实模式。在这个阶段,只有16位,但是借助段寄存器使用超过16位的内存。主要任务,是读取操作系统所在扇区的内存并载入到相应内存位置。我后来用的是0x1000部分的内存(Memory Map)。

读取磁盘:

      读取磁盘只要知道INT 0x13就行了。CH是柱面,DH是磁头,CL是要读的扇区位置, AL是要读的扇区数, AH=02表示读取。关键这里有的DL很坑,代表哪个磁盘,当然是0x00,但是我就傻逼了。我是直接生成img然后当作磁盘来跑,然后死也读不了。原因这时候要设成0x80。还有寄存器地址,主要跟ES和BX有关,具体地址是    ES:BX = ES*16 + BX, 一共fffff位,131072Bytes。还是不够用,这就是BIOS实模式的一个缺点。具体代码都在github

 载入内核:

        这里的内核只是让CPU空转。具体步骤是,读入磁盘内容到内存,找到函数入口的地址(编译后找img中相应字段),然后再修改读完磁盘内容后jump的地址。我的地址是0x4400,作者的是0x4200,然后开始的位置是对应内存0x8000,加起来就是入口地址就是0xc400。jump即可。具体代码github。这个不是重点,重点是我学会了怎么挂载镜像,就像虚拟光驱一样的。并可以写入文件到这个img。

entry

32位保护模式:

      进入保护模式。这个是最复杂的部分,作者挖了个大坑,GDT,这个太复杂了。今天也不想说明了。然后作者的引导方式很奇怪,是要根据编译后的函数入口地址来调节的,很蛋疼,而且好像跟COFF和ELF的格式有关,我试了很久都没办法不用作者的工具成功实验。(我做这个系统的原则是不使用作者的工具)。 后来实在没有办法,我是看了这个指导,重新写了个逻辑结构好的内核。直接调用,编译后直接拼接,免去了上一步,挂载磁盘的麻烦,而且还要读那么多扇区麻烦。这个版本只要读第二个扇区。代码我新建了一个Scratch,说是Scratch,但我感觉要在这个基础上进行下一步了。看看结果。我超前了一点点,把图像显示了一下。

 

video

链接:

  1. boot sector code, LILO
  2. Write a 16-bit os, Tiny bootloader

hadoop2.2 编译安装(64位)

       最近要干正事了,周一要讲论文了。论文有关MapReduce。像我实践派必须要实验一下才能信服。 所以我就安装了hadoop,期间经历比较曲折。。为了稳定,我选择了hadoop 2.2。坑爹的是这个一上来就有个错,下面细说。

  1. 编译选择:

          如果你的机器是32位的,可以不折腾。直接安装编译好的。选个mirror,下载个那个大的就是编译好的。如果64位也直接安装编译好的的话,运行时会报如下Warning:

            这个是因为libhadoop.so.1.0.0是32位的,可以 cd hadoop/lib/native/ ,再 file * ,应该会看到32位。参考文档,只能重新编译。我就整个重新编译了。以下为编译步骤,也可以参考这位大哥的,或者直接看解压后中的BUILDING.txt。

  2. 安装依赖:

    • protobuf : arch可以直接安装protobuf,
    • findbugs: findbugs网上下载,解压后在shell输入: export FINDBUGS_HOME=/path to your extract directory 。不安装的话会有这个错误:
    • 其他依赖,看文档BUILDING.txt。
  3. 修改错误:

    • 参考HADOOP-10110或者这位大哥的。手动将hadoop-common-project/hadoop-auth/pom.xml相应地方改掉,否则会报这个类似错:Failed to execute goal org.apache.maven.plugins:maven-compiler-plugin:2.5.1:testCompile (default-testCompile) on project hadoop-auth: Compilation failure: Compilation failure:
    • 还有一个我遇到的问题,就是maven版本,要改成3.3。不是hadoop问题。见这个博客和这个issue。修改hadoop/pom.xml两处maven版本的地方,3.0->3.3。报错:[ERROR] import: Entry[import from realm ClassRealm[maven.api, parent: null]      [ERROR] [ERROR] —————————————————–:    org.sonatype.aether.graph.DependencyFilter
  4. 编译命令

    • 以上处理完成后,编译就简单了,只要输入以下命令。就可以在 hadoop-dist/target/ 找到你要的东西。
  5. 基本配置

           我使用单点的hadoop,好像现在没psudo模式了。参考这位大哥这位大哥。我把hadoop安装在/opt/hadoop.要注意自己的路径。

    • 添加用户和组
    •  复制安装包
    • 修改配置文件

    • 建yarn节点目录和format node。
    • 写个启动脚本和关闭脚本,或者使用start-all.sh,stop-all.sh, 更好的是start-dfs.sh,start-yarn.sh。还要修改hadoop/etc/hadoop/hadoop-env.sh中的JAVA_HOME。
  6. 测试例子

  • 运行启动脚步,看看http://localhost:19888/,http://localhost:50070/,http://localhost:8088/,看看是否正常。
  • 测试wordcount。 随便搞几个文件,比如start_hadoop.sh,stop_hadoop.sh

mapreducewordcount

       今天大概就这么点,累死我了。这结果还可以在web界面查看,自己摸索。上面的路径我没有特别说明,希望能看得懂。我还遇到个问题是hosts文件要规范,127.0.0.1 localhost 一定要在最前面。。

 链接:

1. hadoop tutorial