h***s
发帖数: 35 | 1 1. 怎样将一个排序的字符串数组分解为两个随机的数组?
小弟的答案是产生随机数,随机数乘数组上限得到index, 拿出index所指的字符串.
重复该过程直到得到一半的字符串.
这个解法的问题是:可能连续产生两个非常接近的随机数,进而产生连续的index, 导
致某些字符串有序.
2. 一个covariance matrix (C), positive definite. what's the exponential of
coveriance, that is, exp(C)?
Hint from interviewer: 1. Taylor expansion; 2. Decompose converiance
matrix.
小弟的答案是: Taylor expansion of exp(C)= 1+C/1!+ C*C/2!+...C^N/N!+...
忽略N阶以上的展开项.
这个解法的问题是:approximation. 面试官要精确精确的结果!!!
小弟不才,恳请高手赐教.非常感谢! | s*******0
发帖数: 3461 | | r*********n
发帖数: 4553 | 3 covariance matrix is not a number. what does it mean to take exp{CovMat}?
element-wise?
【在 h***s 的大作中提到】
: 1. 怎样将一个排序的字符串数组分解为两个随机的数组?
: 小弟的答案是产生随机数,随机数乘数组上限得到index, 拿出index所指的字符串.
: 重复该过程直到得到一半的字符串.
: 这个解法的问题是:可能连续产生两个非常接近的随机数,进而产生连续的index, 导
: 致某些字符串有序.
:
: 2. 一个covariance matrix (C), positive definite. what's the exponential of
: coveriance, that is, exp(C)?
: Hint from interviewer: 1. Taylor expansion; 2. Decompose converiance
: matrix.
| A**u
发帖数: 2458 | 4 2。 cov matrix是实对角矩阵，可以对角化
耐心点，最后求exp(diag1)...,exp(diag2)就可以了，
1. 你说的不对. 开始数组长度是N, 产生1至N的随机数，
当你取出一个数后，下次应该用1到N-1的随机数了.
再下次1至N-2的随机数
【在 h***s 的大作中提到】
: 1. 怎样将一个排序的字符串数组分解为两个随机的数组?
: 小弟的答案是产生随机数,随机数乘数组上限得到index, 拿出index所指的字符串.
: 重复该过程直到得到一半的字符串.
: 这个解法的问题是:可能连续产生两个非常接近的随机数,进而产生连续的index, 导
: 致某些字符串有序.
:
: 2. 一个covariance matrix (C), positive definite. what's the exponential of
: coveriance, that is, exp(C)?
: Hint from interviewer: 1. Taylor expansion; 2. Decompose converiance
: matrix.
| x******a
发帖数: 6336 | 5 第一题什么意思？两个随机数组要满足什么关系么？
【在 A**u 的大作中提到】
: 2。 cov matrix是实对角矩阵，可以对角化
: 耐心点，最后求exp(diag1)...,exp(diag2)就可以了，
: 1. 你说的不对. 开始数组长度是N, 产生1至N的随机数，
: 当你取出一个数后，下次应该用1到N-1的随机数了.
: 再下次1至N-2的随机数
| A**u
发帖数: 2458 | 6 假设原来数组是N大小，
两个随机数组各N/2大小
【在 x******a 的大作中提到】
: 第一题什么意思？两个随机数组要满足什么关系么？
| s***e
发帖数: 267 | 7 For 1 you can use an algorithm similar to random sorting, i.e. pick a
uniform number S1 between 1..N, swap X[1] and X[S1], then pick S2 uniform
from 2..N, swap X[2] and X[S2], .., until you get N/2 done.
For 2 you can decompose C into things like C = U S U^T and the rest should
be easy to compute.
【在 h***s 的大作中提到】
: 1. 怎样将一个排序的字符串数组分解为两个随机的数组?
: 小弟的答案是产生随机数,随机数乘数组上限得到index, 拿出index所指的字符串.
: 重复该过程直到得到一半的字符串.
: 这个解法的问题是:可能连续产生两个非常接近的随机数,进而产生连续的index, 导
: 致某些字符串有序.
:
: 2. 一个covariance matrix (C), positive definite. what's the exponential of
: coveriance, that is, exp(C)?
: Hint from interviewer: 1. Taylor expansion; 2. Decompose converiance
: matrix.
| h***s
发帖数: 35 | 8 Thanks, everyone. The second question has three solutions in Matlab help,
using property: If Y is invertible then eYXY−1 = YeXY−1.
Attach the detail solutions as following:
Matrix Exponentials
For background on the computation of matrix exponentials, see "Nineteen
dubious ways to compute the exponential of a matrix, twenty-five years later
," SIAM Review 45, 3-49, 2003.
The Pseudospectra Gateway is also highly recommended. The web site is:
http://web.comlab.ox.ac.uk/projects/pseudospectra/
Here are three of the 19 ways to compute the exponential of a matrix.
Contents
* Start with the Matrix A
* Scaling and Squaring
* Matrix Exponential via Taylor Series
* Matrix Exponential via Eigenvalues and Eigenvectors
* Compare the Results
* Taylor Series Fails
* Eigenvalues and Vectors Fails
Start with the Matrix A
A = [0 1 2; 0.5 0 1; 2 1 0]
Asave = A;
A =
0 1.0000 2.0000
0.5000 0 1.0000
2.0000 1.0000 0
Scaling and Squaring
expmdemo1 is an implementation of algorithm 11.3.1 in Golub and Van Loan,
Matrix Computations, 3rd edition.
% Scale A by power of 2 so that its norm is < 1/2 .
[f,e] = log2(norm(A,'inf'));
s = max(0,e+1);
A = A/2^s;
% Pade approximation for exp(A)
X = A;
c = 1/2;
E = eye(size(A)) + c*A;
D = eye(size(A)) - c*A;
q = 6;
p = 1;
for k = 2:q
c = c * (q-k+1) / (k*(2*q-k+1));
X = A*X;
cX = c*X;
E = E + cX;
if p
D = D + cX;
else
D = D - cX;
end
p = ~p;
end
E = D\E;
% Undo scaling by repeated squaring
for k = 1:s
E = E*E;
end
E1 = E
E1 =
5.3091 4.0012 5.5778
2.8088 2.8845 3.1930
5.1737 4.0012 5.7132
Matrix Exponential via Taylor Series
expmdemo2 uses the classic definition for the matrix exponential. As a
practical numerical method, this is slow and inaccurate if norm(A) is too
large.
A = Asave;
% Taylor series for exp(A)
E = zeros(size(A));
F = eye(size(A));
k = 1;
while norm(E+F-E,1) > 0
E = E + F;
F = A*F/k;
k = k+1;
end
E2 = E
E2 =
5.3091 4.0012 5.5778
2.8088 2.8845 3.1930
5.1737 4.0012 5.7132
Matrix Exponential via Eigenvalues and Eigenvectors
expmdemo3 assumes that the matrix has a full set of eigenvectors. As a
practical numerical method, the accuracy is determined by the condition of
the eigenvector matrix.
A = Asave;
[V,D] = eig(A);
E = V * diag(exp(diag(D))) / V;
E3 = E
E3 =
5.3091 4.0012 5.5778
2.8088 2.8845 3.1930
5.1737 4.0012 5.7132
Compare the Results
For this matrix, they all do equally well
E = expm(Asave);
err1 = E - E1
err2 = E - E2
err3 = E - E3
err1 =
1.0e-014 *
0.3553 0.1776 0
0.0444 0.0444 -0.0444
-0.0888 -0.0888 -0.3553
err2 =
1.0e-014 *
0 0 -0.2665
-0.0888 -0.0888 -0.0888
0.0888 -0.0888 0
err3 =
1.0e-013 *
-0.0799 -0.0444 -0.0711
-0.0666 -0.0577 -0.0933
-0.0799 -0.0622 -0.1155
Taylor Series Fails
Here is a matrix where the terms in the Taylor series become very large
before they go to zero. Consequently, expmdemo2 fails.
A = [-147 72; -192 93];
E1 = expmdemo1(A)
E2 = expmdemo2(A)
E3 = expmdemo3(A)
E1 =
-0.0996 0.0747
-0.1991 0.1494
E2 =
1.0e+006 *
-1.1985 -0.5908
-2.7438 -2.0442
E3 =
-0.0996 0.0747
-0.1991 0.1494
Eigenvalues and Vectors Fails
Here is a matrix that does not have a full set of eigenvectors. Consequently
, expmdemo3 fails.
A = [-1 1; 0 -1];
E1 = expmdemo1(A)
E2 = expmdemo2(A)
E3 = expmdemo3(A)
E1 =
0.3679 0.3679
0 0.3679
E2 =
0.3679 0.3679
0 0.3679
E3 =
0.3679 0
0 0.3679 | h*y
发帖数: 1289 | 9 LZ needs one more step to get the final answer of Q2:
do an eigen decomposition on C = Q D Q^-1, where D is a diagonal matrix
and C^N = Q D^N Q^-1
so, exp(C) = Q exp(D) Q^-1 | l******n
发帖数: 9344 | 10 fb几天亏了35M,今年的奖金估计没有了
【在 h***s 的大作中提到】
: 1. 怎样将一个排序的字符串数组分解为两个随机的数组?
: 小弟的答案是产生随机数,随机数乘数组上限得到index, 拿出index所指的字符串.
: 重复该过程直到得到一半的字符串.
: 这个解法的问题是:可能连续产生两个非常接近的随机数,进而产生连续的index, 导
: 致某些字符串有序.
:
: 2. 一个covariance matrix (C), positive definite. what's the exponential of
: coveriance, that is, exp(C)?
: Hint from interviewer: 1. Taylor expansion; 2. Decompose converiance
: matrix.
|
|
