More English Towns…

  1. 好多mansion之类的建筑在1832年的riot中被defaced
  2. 在Nottingham郊区还有支持conservatives的牌子; 在Oxford和Cambridge则基本都是vote for Labour, 偶尔也有vote for Green Party, 没有看到过支持Conservative的 (最后果然Oxford and Cambridge的选举结果是万蓝丛中两点红)
  3. Leicester街上阿拉伯人和印度人好多, 街上的车里的司机看着就没几个白人的, 街上的餐馆也基本是印度菜和kebab; Nottingham就好多了, 比较像一个正常的English town; Oxford和Cambridge的中国人就很多了, 有好多家中国餐馆
  4. Oxford比Cambridge compact得多, 所以在Oxford可以靠步行, 在Cambridge就不行了, 必须坐车或者自行车, 比如从Cambridge的老校区去west campus (where 新建的系楼 are located) 超过 1 mile 了.
  5. Cambridge的旅游开发比Oxford多很多, 好多人拿着Cambridge tour的牌子在街上招揽生意. 大概是因为Oxford比Cambridge小很多?
  6. Oxford那些colleges貌似都不让进, Cambridge的话可以进Trinity和St John’s.
  7. Oxford的火车站出来就有一个ox的铜(?)像
  8. Cambridge的一个比Oxford有意思得多的地方是punting tour. 毕竟人家是River Cam, Oxford的那个只是个canal, 水还挺脏的… Both waterways上都有天鹅和鸭 (还可以看到一窝小鸭)
  9. 我们的punter是Trinity College的, 学哲学的, 马上就要毕业了. 被问答他心中的top 5 Cambridge alumni的时候, 他回答说, Alan Turing, Prince Charles (虽然他学得不好), Francis Crick, Stephen Fry, Charles Darwin. (居然没有Newton, Maxwell但是有Fry和Charles!)
  10. Trinity College居然是英国第四大的land owner. 前三分别是monarchy, Church of English和National Trust.
  11. York基本都是白人, 作为旅游城市, 游客不是很多, 而且也主要都是白人
  12. 确实小地方的人nicer. York街上的人就比London的nicer
  13. London的Madame Tussaud里各国政要部分里面没有最近几任的prime ministers. Downing St的背景前面居然是Boris Johnson的蜡像! (是何居心)
Posted in Uncategorized | Leave a comment

Paris

  1. 地铁的ticket machine好些不收纸币, 只能用硬币. 和在很多其他地方一样, ticket machines又confused好些American tourists.
  2. 地铁M1据说不安全, 结果果然车上有各国语言的广播 (法英日中西), 说要照看好自己的belongings. 不过我并没有看到传说中的一群小孩小偷什么的.
  3. Louvre门口还有小心pickpockets的警告, 看来法国的小偷确实很猖獗的样子.20141005_153830
  4. 地铁上经常有人演奏音乐. 半夜的时候可能还有司机在announcement里唱歌.
  5. Paris到处都有merry-go-rounds, 好些还是空转.
  6. Paris的建筑保存得很好, 也都很漂亮, 多数都是圆弧顶的建筑.
  7. 的确通往Sacre-cœur的上山路上有传说中的装聋哑强行要过路人签字捐钱的小孩 (我见到若干美国老太太被坑了). 我的一个朋友遇到了试图强行往过客手上套绳子的黑人, 不过我没有遇到. 看来不同上山道路的tourist traps不一样. 通往Sacre-cœur的正面有缆车的那条路没有这些问题.
  8. Louvre的paintings真的非常impressive, 全世界估计没有另一个地方能跟这个相提并论了. 不过几个特别著名paintings (比如Mona Lisa) overshadow了几乎其他全部画, 其他画基本都没人看.  Mona Lisa前面人山人海, 同一个展厅的Mona Lisa对面的Marriage at Cana就没什么人理睬了…
    P1010401
  9. Louvre也非常大, 里面比British Museum宽阔很多. British Museum还是太挤了. 埃及和希腊的东西还是British Museum比较好. 在British Museum的时候guide说了很多雕塑的头在这里但是身体在Louvre, 这次发现果然Louvre里面一堆没有头的sculptures.
  10. Louvre内部装潢奢华 (毕竟原来是宫殿). British Museum就是一个普通博物馆.
  11. Paris找厕所不太容易, 为此居然还有一个专门的Toilets in Paris的app. 虽然街上到处都有café, 可以花钱买coffee然后用café的厕所, 但是星期日很多店并不营业…
  12. Paris街上也没有像英国和美国那样那么多的convenience store, 所以买水只能去 cafe 或者 bakery 买很贵的水 (500ml 要 1.6 EUR – 2 EUR)
  13. Paris街上可以看到统一样式的免费厕所. 那种厕所在一个人用完以后会自动清洗(包括清洗地板)然后下一个人才能再用. 所以很慢, 前面8个人的话可能会等上20+分钟.
  14. 卖postcards的小店都不卖邮票. 邮票要去烟店买.
  15. Paris满街bakeries. Baguettes果然很popular, 早上看到好多法国人在bakery买baguettes, 用一个很长的袋子装了就走.
  16. Paris地铁的车比London tube透气得多, 但是stations的装修不如London tube的新
  17. Paris地铁站很密, 走几步就一个站, 走几步就一个站
  18. 虽然Paris是fashion之都, 但是街上的人感觉穿得也就那样. 反而Londoners都穿得普遍比较高端一点. 有social classes就是不一样啊
  19. 总体上感觉Paris不如London, 因为London看着就forward-looking, Paris完全不给人这个感受.
Posted in Travel | Leave a comment

London

A man’s mind grows narrow in a narrow place, whose mind is enlarged only because he has lived in a large place: but what is got by books and thinking is preserved in a narrow place as well as in a large place. A man cannot know modes of life as well in Minorca as in London; but he may study mathematicks as well in Minorca. (by Samuel Johnson)

  1. 真是transport的天下 (这里的transport指的是一种typeface), 配以一些Helvetica
  2. 对游客very friendly, 各种信息一目了然, 不像NYC… 地铁经常临时改线什么的, 而且都没有文字通知, 都是广播, 而且还是根本听不清楚说什么的黑人口音
  3. 过街的时候路面上会有提示说’look right’ or ‘look left’, 估计是因为来自左行国家的游客太少了吧, 不过这点还是很温馨的
  4. tube系统也很好, 虽然老的线没有空调, 如果外面25C下面就会很热… 而且也有signal failure之类的造成的delay; 但是NYC的地铁跟London tube一比还是只能用pathetic来形容
  5. House of Parliament之类的建筑从电视上来真看不出来什么, 但是到了当地亲眼看到觉得墙上的那些decorations还是非常震撼的
  6. Buckingham palace还有tower of London里面的那些展览也是, 非常impressive
  7. British museum非常非常大, 感觉至少可以看2天; 不过博物馆什么的还是跟着guided tour好, 一般来说一个room的展览就可以讲45min, 然后大概15个rooms有这样的tour, 所以算下来至少2天
  8. British museum里还有bible tour, 一堆人去museum里找文物支持bible的说法
  9. Metroplitan跟British museum比就逊多了, 埃及/中东/希腊/罗马/中世纪欧洲的东西还是British museum的东西多得多
  10. 居民住宅果然以terraced houses为主, Warwick square之类的地方一整条街一整条街的terraced houses, 看着很neat和graceful.
  11. London总体来说人不很多, 除了几个主要的游客经典外, 大把地方是寂静的住宅区; 比NYC好多了, NYC实在compact. 不过London的pharmacies没有NYC那么多, 走几步就一个的程度
  12. 英国人民太文艺了, 地铁的notice board居然放这个东西, 还是black letters:
    P1010182
  13. 此外Westminster Station的厕所里也有壁画
    P1000997
  14. Trafalgar station的入口走道也有壁画, 就不贴出来了…
  15. 基本上英国吃一顿饭£10-13这样; 500/750ml的水一瓶75p – £1.40这样
  16. 英国的饮料瓶没有deposit; 回收工作还是做得不够好; 垃圾分类也做得不够好, 街上很少见分类的垃圾箱
  17. 夏天游客好多, 有好多summer school的小孩, 主要是中国人和韩国人
  18. Royal observatory外面居然有jehovah见证人中文传教
  19. 终于见到了NCE课文里的Cutty Sark, 不过没有看到木头rudder, 好失望
  20. 不过在Maritime museum里的特别展览里见到了Harrison的表, H1 to H3原件, 还是很impressive
  21. 街上的postcards几乎全是风景/王室肖像postcards, 只看到British museum外面的一个店和cards galore(这是连锁店)卖‘How to be British’系列的postcards
  22. Harrods果然高端大气上档次, escalator well都弄得金碧辉煌
  23. 看到了Fabian society的小楼还有east india company的店(好像主要卖茶叶)
  24. London的街上好多free wifi接入点 (每次free半小时), 这种infrastructure比美国不知道强到哪里去了
  25. 商店信用卡的主要模式是chip + signature, 不是所有的机器都可以刷磁条, 因此最好要有chip卡. 营业员真的会比对signature, 所以去超市self check-out的时候那个系统也要叫营业员来比对signature, 即便是只买1 quid的东西, 这点是有点麻烦.
  26. 2o14年7月起所有buses不再接收现金支付, 所以要么用oyster card或者daytravel card, 要么用带contactless payment功能的credit card
  27. 整个城市四处都是historic buildings之类的, 可以看的东西实在太多了, 感觉要至少一周时间才能好好玩. 因为时间关系, 没赶上London bridge的lift time; 这次也没空去Windsor castle, 只能希望以后补了; 还有好多小东西也没发去找了(比如各种gentlemen’s club)
Posted in Travel | 2 Comments

Heidelberg

绝大多数人都是奔着那个castle去的. 除了火车站就乘bus然后转cable car就到castle了. 大多数部分是19世纪的时候重建的, 因为原来的在Louis XIV时期的战争中被法国人烧毁了. 不过重建的时候, 当时人们也不清楚以前的furnishings之类的是什么样子, 所以是根据想像重建的, 结果就掺入了baroque和roccoco元素.

P1000622进入城堡参观需要参加guided tour. 参加的好多都是美国人, 不知道为什么Heidelberg在美国人那里好像很流行的样子, 德国人都知道Heidelberg有好多美国游客. 那个guide先问了下大家都是哪国人然后发现没有法国人就开始说法国人坏话了, LOL. 那个guide还说以前英国和Heidelberg关系很好 (毕竟是亲戚关系, 现在复原的房间内就有George I的祖母的画像) 因为双方都hate the French, 众人笑. 然后一个Irish游客在下面说it still carries on today.

那个guide还说原来elector的private chapel现在变成了举办婚礼的场所, 在日本人间特别流行. 说日本人特别喜欢基督教式的婚礼, 搞个牧师(不管真假)来主持然后交换戒指什么的. Heidelberg在日本人旅游的欧洲城市里算top 10, 德国还有另一个城市日本人也很爱去办婚礼, 不过我没听清楚名字. 那个guide说这种wedding toursim让Heidelberg赚了很多钱.

贵族就是奢侈, 连fireplace都是ceramic… fireplace添加木材和煤的地方在室外, 这样贵族在房间里就不会看见servants了.

以前放cannons的地方室内高度都非常高, 而且头顶的砖头都有孔, 是为了让smoke散出去. 此外中世纪的spiral staircase下楼时总是逆时针的, 因为这样便于在上层的人挥剑防守从下面进攻的敌人. Castle的城墙部分的砖头都有小孔, 因为砖头很重, 打个孔然后可以从中插入一个杆这样两个人容易把砖头抬起来.

以前这些big construction主要是在冬天进行, 因为冬天农民没事做就被抓来造房子…

Castle有个cellar, 里面有一个巨大的wine barrel, 据说是以前用来放所收的tithe wine的 (所以里面存的是各种wine的mixture). 周围的墙上就是各种涂鸦了, 主要内容是各地的人到此一游和情侣秀恩爱(一个心里面写着两个人的名字). 后来去了那个Bismarck Tower (本来以为能鸟瞰Heidelberg结果发现被周围的树挡住了) 也看到了情侣秀恩爱: 把一个锁锁在什么handle上, 然后在锁上刻了双方的名字.

Heidelberg的古城的street sign的字体居然是Garamond. 第一次看到Garamond用在路标上, 果然够复古. 根据小写a, r和t来看好像是Stempel Garamond. 古城有Uni of Heidelberg的一个校区, 这个校区好像都是研究历史/文物的系, 比如classical archaeology和papyrology(第一次见到这个系).

P1000640

Posted in Travel | 1 Comment

德美比较 on first impressions

在Saarbrücken呆了4天了, 顺便一记初印象. 下面内容里出现的价格以2014年1月21日-26日的为准, 除非特别注明.

  1. 每天0C-5C这样, 湿度很大, 室内暖气开到20C湿度仍然可以保证; 真是比Ann Arbor和Berkeley不知道好到哪里去了
  2. 从Frankfurt到Saarbrücken的沿途都是森林和水, 外加阴天, 很好看; 比美国乡下好看
  3. Saarbrücken有很多碎石子路面, 很多上面也长了苔藓, 有时走路会滑; 美国倒没见这样的, 可能东北部有, 但是东北部之外的广大的文化沙漠之地就没有了
  4. 超市没有Fuji apples; 总体来说蔬菜水果不如美国. Organic水果和蔬菜的个头小于美国的.
  5. 德国人的超市里有亚洲的米, 但是没有亚洲的面, 面只有pasta
  6. 德国好像还蛮流行洗衣机的消毒液的
  7. 德国超市里需要冷藏的食品都有标注冷藏的最高温度
  8. 德国的无酒精洗手液没有triclosan这个成分, 而是benzalkonium chloride (BZK). BZK对水生物有毒, 高剂量时对哺乳动物也有, 超过10%的浓度就对人有毒. EU貌似不让用triclosan. Triclosan会降解成为有毒的dioxin, 而且近年来也开始被怀疑可能致癌. 所以洗手还是用水和肥皂吧.
  9. 德国厕所里的擦手纸比美国的柔软, 但是一般的public toilet都不免费, Mc里的一次要收50 euro cents.
  10. 这里的cashiers, bus drivers, 商店里的大多数assistants都不会英文. 感觉是没有上过某种学校的就不会英文. 年龄大一些的也不会, 年轻人好很多. 所以出门办事就找身边有没有年轻人, 让他做翻译. 居然Bürgeramt (类似于中国的户籍管理所)里的人也不会英语, 所有外国人都要去那里注册的啊!
  11. 德国这里的pastry里我还没有看到含high fructose syrup, 在美国已经流行了30+年的用high fructose syrup代替糖的practice因为EU的限制所以不成气候. 这点蛮让人放心的. 中国也不流行high fructose syrup, 当然中国的东西不够甜.
  12. 德国人好像不喜欢用烘干机, 都是晾干的. 晾衣架和阳台差不多高, 这样可以防止阳台上彩旗飘飘的观感.
  13. Deutsche Bank的系统要求客户的姓和名都要至少3个字母…
  14. 德国的drugstore (drogeurie)不卖西药, 但是卖各种草药提取物; 什么治支气管炎的药啦, 感冒药啦, 咳嗽药啦, 在drugstore里都只能找到草药提取物的. 德国人确实相当迷信草药啊, 难怪德国在草药提取物的研究处于世界前列.
  15. 要买正经的西药要去专门的apothecary. 这点不如美国把OTC直接摆在drugstore和超市里让顾客自己挑来得方便.
  16. 德国貌似没有牙线宽的floss picks, 网络上也没有… 英国的网络上就很多这个了
  17. Eucerin虽然是德国的牌子, 但是德国这里找不到Aquaphor这个子品牌, 原因不明. 难道Aquaphor含有什么EU禁用的东西? 不过为什么就连Eucerin也要去apothecary才有, drugstore就没有呢… 估计只能用Eucerin的某种salve当替代品了, 但是我担心它仍然不够油.
  18. 德国有一种看起来很不安全的支付方式, 告诉对方银行号和账号, 对方就可以从账号上扣钱… 这信用制度好像比美国的强多了啊
  19. 德国的窗果然是有两种开法的, 见 http://www.douban.com/group/topic/43435102/ 的第2点
  20. 德国果然是DHL的天下, 但是redeliver一个missed parcel需要隔一个工作日才可以
  21. Saarbrücken的人口密度远不如Ann Arbor (807 v.s. 2653 人/km^2), 但公交系统比Ann Arbor的不知道高到哪里去了. 不过公交也蛮贵的, 单程一次2.5EUR, 短程单程(不超过5个站)1.9EUR. 所以要果断办月票, 57ish EUR每月.
  22. Saarland的食堂不错, 4.2 EUR一餐, 有汤, 主菜, rice pudding, 而且比UMich的Pierpont Commons二楼$5.95的好吃无数.
Posted in Uncategorized | 3 Comments

weak \ell_1 norm in sparse recovery

Regarding the sparse recovery problem, it is difficult (and remains open) to find a sub-linear algorithm to achieve the mixed norm \ell_2/\ell_1 error bound

\displaystyle\|x-x'\|_2\leq \frac{1}{\sqrt{k}}\|x-x_k\|_1

using the optimal number of measurements, i.e., O(k\log(n/k)) measurements. The polynomial-time algorithm simply returns the minimiser x' of the following minimisation problem

\min_y \|x-y\|_1 s.t. \Phi x = \Phi y.

Current techniques of sub-linear algorithm is to hash the heavy hitters in to bucket, hoping that each bucket contains exactly one heavy hitter. Existing efforts for \ell_2/\ell_1 problem all lead to extra log factors in the number of measurements, which suggests that this approach may have its limits for the \ell_2/\ell_1 problem, so we pose a natural question: can we relax the \ell_1 norm on the right-hand side so hashing-based sub-linear algorithms achieves the optimal number of measurements? A natural candidate is the weak \ell_1 norm (denoted by $\ell_{1,\infty}$), which is smaller than \ell_1 norm but larger than any \ell_{1+\epsilon} norm. So the question is, what is the minimum number of measurements which guarantees

\displaystyle\|x-x'\|_2\leq \frac{1}{\sqrt{k}}\|x-x_k\|_{1,\infty}?

Since for x\in \mathbb{R}^n it holds that (\log n)\|x\|_1\leq \|x\|_{1,\infty} (equality is attained when x=(1,1/2,1/2,1/4,1/4,1/4,1/4,...), in general, 2^n coordinates of magnitude 2^{-n}) one might be tempted to think that the optimal number of measurements would increase by a \log n factor. This is not the case, however, as the usual RIP matrix would work, by replacing the \ell_1 norm in the minimization problem above with the weak \ell_1 norm.

For the \ell_1 norm it is known that the head of 2k coordinates is already a good approximation:

\displaystyle\|x-x_{2k}\|_2\leq \frac{1}{\sqrt{k}}\|x-x_k\|_1.

The proof is to break up the tail into blocks of size k. This is also the core technique in the proof of \ell_1 recovery, as the RIP property guarantees that \Phi preserves the \ell_2 norm of each block.

We desire something similar for the weak \ell_1 norm. It is natural to ask first if a head of size O(k) (not O(k\log n), which is trivial by the argument above) serves as a good approximation, that is, does there exist some numerical constant C such that

\displaystyle\|x-x_k\|_2\leq \frac{C}{\sqrt{k}}\|x\|_{1,\infty}

for all x? This is true, actually with C=\pi^2/6. The proof is the same, breaking up the tail into blocks of size k. We shall show that

\displaystyle k\|x-x_k\|_2^2 \lesssim \|x\|_{1,w}^2 = \max_i i^2 |x_i|^2

assuming that x_1\geq x_2\geq x_3\geq \cdots. Now the LHS is at most k^2(|x_k|^2+|x_{2k}|^2+\cdots) and the RHS is at least \max_i (ik)^2 |x_{ik}|^2, hence it suffices to prove the following claim.

Claim. For x_1\geq x_2\geq \cdots \geq 0, there exists numerical C such that \sum x_i^2 \leq C\max_i i^2x_i^2.

Proof. We show that it holds with C>\pi^2/6. Suppose not, then S:=\sum x_i^2\geq C\max_i i^2x_i^2, then x_i^2\leq S/(i^2C) for all i. Summation over i gives S\leq S/C\cdot \pi^2/6 < S, a contradiction. Hence S \leq C\max_i i^2 x_i^2.

Then, using this trick in the block argument we can show that

Lemma. For RIP matrix \Phi with appropriate parameters, if \Phi x = 0 then

\displaystyle\|x_{3k}\|_2\leq \frac{C}{\sqrt k} \|x-x_{2k}\|_{1,\infty},

where C depends on the RIP parameter \delta of \Phi.

Together with the already established

\displaystyle\|x-x_{3k}\|_2\leq \frac{C'}{\sqrt k} \|x-x_{2k}\|_{1,\infty},

we obtain the null space property of RIP matrices with mixed norm \ell_2/\ell_{1,\infty} that

Lemma (null space property)For RIP matrix \Phi with appropriate parameters, if \Phi x = 0 then

\displaystyle\|x\|_2\leq \frac{C}{\sqrt k} \|x-x_{2k}\|_{1,\infty},

where C depends on the RIP parameter \delta of \Phi.

It follows from a similar argument as in [Cohen, Dahmen and DeVore 2006] that the mixed norm \ell_2,\ell_{1,\infty} problem can be solved with O(k\log (n/k)) measurements by RIP matrices as well. However, an efficient algorithm is not known.

Posted in Mathematics | Leave a comment

Master of the House

Obsessed with the musical les Miserables for a few days. Having listened to Master of House repeatedly of both 10th and 25th anniversary edition, I came to notice the following inconsistencies in h-dropping of Thénardier (played by Alun Armstrong and Matt Lucas respectively).

10th anniversary: h is dropped in all places except in house in his solo, but it is dropped in chorus.

25th anniversary: h is retained in most occurrences, including how, house and handshake and one occurrence of here. The h in house is dropped in chorus as well.

Posted in Uncategorized | Leave a comment