|
h****g
发帖数: 772 | 2 【 以下文字转载自 Mathematics 讨论区 】
发信人: huangg (水银泻地), 信区: Mathematics
标 题: 对任意mXn的矩阵M，能否找到两个对角阵P,Q,使PMQ=I, QM'P=I
发信站: BBS 未名空间站 (Wed Feb 27 22:42:19 2013, 美东)
能不能呢？这个命题对吗？
如果可以的话，怎么求出P和Q呢？
问题来源于SVD分解，SVD能从V矩阵判断是不是有一个向量dominate,那么能否对各个向
量找到一个scale factor，使他们的singular value都是1呢？
对新矩阵做SVD,应该得到M1=S1V1D1,就我想象，应该是这个P和Q把向量的scale factor
都包括了，然后新的S1和V1是旋转坐标，应该得到都是1的奇异值，
这对吗？
谢谢 |
|
h****g
发帖数: 772 | 3 【 以下文字转载自 Mathematics 讨论区 】
发信人: huangg (水银泻地), 信区: Mathematics
标 题: 对任意mXn的矩阵M，能否找到两个对角阵P,Q,使PMQ=I, QM'P=I
发信站: BBS 未名空间站 (Wed Feb 27 22:42:19 2013, 美东)
能不能呢？这个命题对吗？
如果可以的话，怎么求出P和Q呢？
问题来源于SVD分解，SVD能从V矩阵判断是不是有一个向量dominate,那么能否对各个向
量找到一个scale factor，使他们的singular value都是1呢？
对新矩阵做SVD,应该得到M1=S1V1D1,就我想象，应该是这个P和Q把向量的scale factor
都包括了，然后新的S1和V1是旋转坐标，应该得到都是1的奇异值，
这对吗？
谢谢 |
|
h****g
发帖数: 772 | 4 【 以下文字转载自 Mathematics 讨论区 】
发信人: huangg (水银泻地), 信区: Mathematics
标 题: 对任意mXn的矩阵M，能否找到两个对角阵P,Q,使PMQ=I, QM'P=I
发信站: BBS 未名空间站 (Wed Feb 27 22:42:19 2013, 美东)
能不能呢？这个命题对吗？
如果可以的话，怎么求出P和Q呢？
问题来源于SVD分解，SVD能从V矩阵判断是不是有一个向量dominate,那么能否对各个向
量找到一个scale factor，使他们的singular value都是1呢？
对新矩阵做SVD,应该得到M1=S1V1D1,就我想象，应该是这个P和Q把向量的scale factor
都包括了，然后新的S1和V1是旋转坐标，应该得到都是1的奇异值，
这对吗？
谢谢 |
|
发帖数: 1 | 5 笑死了，那不是結論，那只是最後一個指標。前面幾個指標，中國都比墨西哥差，只有
最後一個和倒數第三個，中國比墨西哥強。如果看最重要的生活成本（房價），中國房
價是墨西哥4倍，人均GDP還沒墨西哥高，中國老百姓真苦。
Buy Apartment Price
Price per Square Feet to Buy Apartment in City Centre 2,307.33 MXN
(844.18 ￥) 11,867.89 MXN
(4,342.11 ￥) +414.36 %
Price per Square Feet to Buy Apartment Outside of Centre 1,528.39 MXN
(559.19 ￥) 6,730.92 MXN
(2,462.65 ￥) +340.39 % |
|
k****g
发帖数: 67 | 6 如果已知矩阵A的svd分解U*S*V^T
其中A, U, S, V的大小分别是mxn, mxn, nxn, nxn
如何利用这些信息构造null(A)?
ps: 如果svd能分解出 U_{mxm}, S_{mxn}, V_{nxn}，我就会构造，
但是网上找的代码都只能生成economy size的分解，郁闷 |
|
w********9
发帖数: 8613 | 7 Average Monthly Net Salary (After Tax) 9,522.77 MXN
(3,484.10 ￥) 16,861.94 MXN
(6,169.29 ￥) +77.07 %
==> 1.7707
Consumer Prices Including Rent in China are 20.82% higher than in Mexico
(包含了所有的销费指标，也就是所有那些分项。见前面的英文解释）
==> 1.2082
1.7707/1.2082-1
===========
46.55% |
|
i**********e
发帖数: 1145 | 8 你上面的list我也没看懂。
补充一下我知道的一些经典的dp题：
LIS (longest increasing subsequence),O(n^2) DP, O(n log n) binary search加速
优化。
Edit distance.
Minimum path sum. 就是一个 MxN 矩阵，求从左上角到右下角的最小 sum.
当然还有经常问的 Unique paths, MxN 矩阵 从左上角到右下角总共有多少条路径。 |
|
m*****y
发帖数: 93 | 9 建一个visited matrix然后bfs, 时间O(mxn)空间O(mxn) |
|
s********o
发帖数: 3783 | 10 面试遇到的题目有非常多都是leetcode原题
比如我上面提到的2sum，跟leetcode一模一样，一模一样的我就不说了。
下面是一些题，不分先后，不分公司，全混在一起说
1，leetcode 2sum，用O(nlogn)和O(n)怎么做
2，leetcode 2sum，如果是小于不是等于怎么做，3sum怎么做，小于x怎么做
4sum怎么做，小于x怎么做，只输出符合条件（小于x）的总个数但是不需要输出具体数
怎么做，不但输出总个数还要输出具体答案怎么做，k sum 小于x怎么做，
k sum有没有多项式解？证明之
3，一个城市的地图（mxn矩阵），求从左上到右下一共有多少种可能的路线（只能向右
和向下）。先用程序写（利用通项公式递推），然后让我在白板上写close form公式
其实close form非常非常简单，只不过我没见过这道题，当场没有看出来。但是我硬挺
着从通项公式开始用矩阵分解去求解close form，最后在面试官的一点帮助下还是写出
来了公式，最后面试官表示我的数学基本功非常令他吃惊。（我心里想好歹也是学过几
门数学课的）。。。
4，还是数学题，求k个数的最大公约数... 阅读全帖 |
|
d**********6
发帖数: 4434 | 11 我老师介绍的办法是这样的，假设一个mXn的sorted matrix，目标t
他的从左上到右下的对角线也是sorted的，用一个binary search找到比t大和比t小的
两个临近点p1, p2
然后p1往后行又binary search
p2往前整行又binary search
复杂度是 O(log(sqrt(mXn))) + O(log(n)))
应该比那个人总结的都好啊 |
|
n*******1
发帖数: 2254 | 12 typical beixiao mxn - reminds me of the "2nd chance" comment from another
beixiao mxn... |
|
J*******u
发帖数: 531 | 13 在Travelocity上找了一个最便宜的Payless Car Rental，然后非要叫我一天17美元买
Liability Insurance，说是必须要买的，可是我travelocity上的rules如下，我理解
是租车的钱已经自带25k的liability了，而高额的750k的是可选的，不一定要买的，对
吗？
可惜当时没有Internet，无法pull这个rule，就暂时先接受了，如果我的理解没错，我
可以找credit card company argue回来吗？虽然钱也不多，不过这样强加消费真的不
舒服。。。
insurance
LIABILITY INSURANCE PROTECTS YOU AGAINST CLAIMS FOR INJURY
OR DAMAGE YOU CAUSE TO THIRD PERSONS OR THEIR PROPERTY.
IT DOES NOT COVER INJURY TO YOU OR DAMAGE TO THE RENTED
VEHICLE. PROPERTY DAMAGE/PUBLIC LIABILITY IS INCLUDED I... 阅读全帖 |
|
g******s
发帖数: 733 | 14 比如要一个 1*3的向量,乘一个3*100的矩阵.
向量的第i个元素乘矩阵的第i行,结果为3*100的矩阵. 请问不用for循环matlab能行吗?` |
|
g***i
发帖数: 90 | 15 many ways. one:
diag(v)*A |
|
g******s
发帖数: 733 | 16 you are really an expert! Thank you so much!
吗?` |
|
g******s
发帖数: 733 | 17 请问怎样从一个3*100 的矩阵的第 i 行减去一个长度为3的向量的第i个元素? 好象这个
不用循环是不行了.
行 |
|
l*****i
发帖数: 3929 | 18 A=A-diag(v)*ones(size(A)) |
|
r****y
发帖数: 1437 | 19
Let a is your vector, and B is the matrix,
repmat(a', 1, 100) .* B |
|
r****y
发帖数: 1437 | 20
B - repmat(a', 1, 100)
You really need to learn some basic about matlab ah. |
|
w**d
发帖数: 2334 | 21 why bother? In the new version of Matlab, for loop won't slow your program
down. |
|
|
w**d
发帖数: 2334 | 23 i need to dig out my notes. It might be related to the issue of memory.
A senior engineer from mathworks once gave
several lectures on Matlab. He told us so. |
|
s***t
发帖数: 195 | 24 as far as i know, the matrix operations in matlab are implemented with BLAS.
plus matlab is an intepreter, not a compiler (i know you can compile matlab
code, but it's another story). these two reasons make it hard to believe
for loops are as fast as matrix operations in matlab.
i would certainly want to know any new development in matlab. |
|
w**d
发帖数: 2334 | 25 i know it is hard to beat BLAS. In my understanding, the for-loop might be not
as effecient as BLAS, but won't be slower than the standard for-loop in C or
Fortran.
But the main reason for the slow speed of for-loop is because during
the for-loop, lots of intermediate variables are generated.
In the new version, it is not done in that way if the matrix variable
has been initialized.
Mathworks has done something to improve the speed. You can go to the website of mathworks, and search with
keywor |
|
s***t
发帖数: 195 | 26 sorry, just read my post again. it seems i always left some critical words
in my sentences. i meant to say "i would certainly WANT TO know any new
development" :)
anyways, why search for "jitter"? isn't it variation in sampling time? i
searched and didn't see many relavant results. can you give some links? |
|
A**u
发帖数: 2458 | 27 quant面试真好
随便问啊
不会做，有个类似的题目，做过，看有帮助没
选m,n列，有mxn个交点
组成mxn的子矩阵，不一定连续的
有一个道题目，找最大和的子矩阵, DP 你搜搜 |
|
s**********e
发帖数: 33562 | 28 http://edition.cnn.com/2014/06/02/asia/gallery/jeff-widener-gal
A day after the military opened fire on protestors, photographer Jeff
Widener was setting up the shot for the now iconic "txxk mxn" image: "I was
leaning over the balcony aiming at this row of tanks, and the guy walks out
with this shopping bag and I was thinking 'the guy is going to ruin my
composition.'" The final photo won the Scoop Award in France, the Chia
Sardina Award in Italy, and was a finalist for the Pulitzer Prize.
Thi... 阅读全帖 |
|
发帖数: 1 | 29 给定MxN二维数组表示地图
用0表示可通行 1表示是障碍
给定两辆坦克a,b 起始坐标
坦克各自可上下左右移动 一次走一格
两坦克行进中至少相隔一格距离！
再给定两个目标A，B坐标
请设计一个算法：
输入地图，以及坦克a,b, 和目标A, B 的坐标
输出：两辆坦克都抵达目标， 最小所需步数
注：
非码工索南，给出任意解法即可。
码工索南，要求线性时间复杂度。
example：
b 0 0 A 1 0 0 0
0 0 0 0 1 0 0 0
0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0
0 1 1 1 0 0 0 0
0 0 0 0 a 0 0 0
0 0 B 0 0 0 0 0 |
|
发帖数: 1 | 30 全球最强！阿里巴巴宣布研制出量子电路模拟器“太章”
新智元发表于2018年05月08日 03:576292人阅读
摘要: 5月8日，阿里巴巴量子实验室施尧耘团队宣布成功研制出当前世界最强的量
子电路模拟器，名为“太章”。 过去超级计算机做不了的模拟任务，如64（8x8）比特
40层的模拟，“太章”只需2分钟即可完成。
5月8日，阿里巴巴量子实验室施尧耘团队宣布于近日成功研制当前世界最强的量子电路
模拟器，名为“太章”。 基于阿里巴巴集团计算平台在线集群的超强算力，“太章”
在世界上率先成功模拟了81（9x9）比特40层的作为基准的谷歌随机量子电路，之前达
到这个层数的模拟器只能处理49比特。
量子霸权似乎在上演一场“接力战”。
2月，IBM对外展示了其50个量子比特原型机，内部结构图也曝光；
3月，谷歌公布72位量子比特处理器Bristlecone。
3月底，微软发现天使粒子——马约拉纳费米子（Majorana fermion）存在的有力
证据，有望年底前得到可工作的量子比特。
现在，轮到阿里上场了。
5月8日，阿里巴巴量子实验室施尧耘团队宣布于近日成功研制当前世界最强的量子电... 阅读全帖 |
|
c********i
发帖数: 1489 | 31 No, USD/MXN dropped.
Watch @ES, SPY tomorrow for the real clue.
Wall street still has time to do the real hedging. |
|
|
|
|
s***d
发帖数: 15421 | 35 trump 表现的不错,至少 usd/mxn 涨的不错. |
|
s***d
发帖数: 15421 | 36 觉得不好的 都是8020 任务的, usd.mxn debate期间的 汇率最能作为real time poll |
|
|
|
|
d***d
发帖数: 1 | 40 这是我遇到的google面试题目,希望后来者好运.
1.求直方图的最大内接矩形,假设每个细条的宽度为1.这个题很hot,两个人来问.我没想
出什么好的算法.
2.NxN行列有序的矩阵查找一个数.以前有人遇到过.O(N)的时间复杂度
3.给定一篇文章,求包含所有单词的最短摘要.O(N)的时间复杂度
4.将MxN的矩阵转秩,要求O(1)的空间复杂度.参考群论中cyclic group,group
generator
5.开放式问题,怎么避免重复抓取网页
6.开放式问题,有些网站每天只允许有限次访问,怎么抓取网页使得索引尽量全面和新鲜
7.写一个singleton pattern的例子
8.vector vs. arraylist, growth strategy & complexity
9.在C++文件中只declare class A, 但不以任何方式define class A, 是做什么用
10.virtual function
11.讨论html vs. xhtml vs. xml
12.描述在浏览器中敲入一个网址后所发生的事情.dns,cache等 |
|
t**e
发帖数: 208 | 41 来自主题: JobHunting版 - 问个算法题 you are given a M x N matrix with 0's and 1's
find the matrix with largest number of 1,
1. find the largest square matrix with 1's
2. Find the largest rectangular matrix with 1's
要求O(MxN), 怎么解?谢谢～～～ |
|
R***r
发帖数: 120 | 42 一个MxN的Matrix，从左上角向右下角移动，每次移动只可以向右或向下，求总共有多
少条不同的路径，如4x3的话是10条。有公式可以套么？谢谢。 |
|
c***z
发帖数: 6348 | 43 Q1. Describe one of your projects.
Q2. Why the copy constructor pass by reference not by value?
I said I know the general difference between passing by reference (globe
copy) and value (local copy), but I don't know if it applies here.
He told me that if I pass by value and the value is an object of another
class, then there will be an infinite loop.
(I bombed this one I think.)
Q3. Given an MxN binary matrix, how to find a max all 0 square submatrix?
I started with the naive approach (go along |
|
c***z
发帖数: 6348 | 44 I finally made it. Anyone care to check it up? :)
/**************************************************************
Maximum all-0 square submatrix problem -- Compiled under VC++ 2008.
Problem Description:
Given MxN binary matrix M, find the maximum all 0 square submatrix (
denoted by MASS) of it.
Example:
0000100
1100100
0000011 <= an answer is the 3x3 submatrix (row 2~4, col 0~2)
0000010
0000100
0010100
Algorithm Description:
The key idea is Dynamic Programm |
|
c***z
发帖数: 6348 | 45 I worked out the rectangular algorithm. I feel that I like these problems,
but... I am too slow I think...
/**************************************************************
Maximum All-0 Submatrix Problem (not necessarily square submatrix)
-- compiled under VC++ 2008
Problem Description:
Given MxN binary matrix R, find the maximum all 0 submatrix (not
necessarily square submatrix, denoted by MAS) of it.
Example:
0000100
1100100
0000011 <= an answer is |
|
c***z
发帖数: 6348 | 46 方阵的话用Dynamic Programming
/**************************************************************
Maximum all-0 square submatrix problem -- Compiled under VC++ 2008.
Problem Description:
Given MxN binary matrix M, find the maximum all 0 square submatrix (
denoted by MASS) of it.
Example:
0000100
1100100
0000011 <= an answer is the 3x3 submatrix (row 2~4, col 0~2)
0000010
0000100
0010100
Algorithm Description:
The key idea is Dynamic Programming. Assume we are going |
|
c***z
发帖数: 6348 | 47
非方阵的我也做出来了，可是还是没有用。从此以后我就没有信心了。。。
/**************************************************************
Maximum All-0 Submatrix Problem (not necessarily square submatrix)
-- compiled under VC++ 2008
Problem Description:
Given MxN binary matrix R, find the maximum all 0 submatrix (not
necessarily square submatrix, denoted by MAS) of it.
Example:
0000100
1100100
0000011 <= an answer is the 2x5 submatrix (row 0~4, col 2~3)
1000010
0000100
001010 |
|
i**9
发帖数: 351 | 48 一道老题，求最大square 可以用 DP
http://geeksforgeeks.org/?p=6257
Let the given binary matrix be M[R][C]. The idea of the algorithm is to
construct an auxiliary size matrix S[][] in which each entry S[i][j]
represents size of the square sub-matrix with all 1s including M[i][j] and
M[i][j] is the rightmost and bottommost entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use foll... 阅读全帖 |
|
|
i**9
发帖数: 351 | 50 Thanks!
(search for maximal rectangle)
problem |
|
