Giờ em đang tập tành research đây, ngành của em là EE, cái em định làm là Compressed Sensing (CS). Nói một cách tóm tắt bài toán này thực hiện việc sau đây, cho y = A*x trong đó x là vec tơ N*1, K-sparse, A là matrix có kích thước m*N (m<<N), và y là vec tơ m*1
Vấn đề cần giải quyết là làm thế nào để từ y và A ta có lại được x' sao cho ||x' - x|| < \epsilon cho trước. Nhấn mạnh lại lần nữa là x có K sparse << N.
Em tạm thời xác định ra bai bài toán nhỏ cần quan tâm:
Một là xây dựng ma trận đo A như thế nào để có thể khôi phục được x' với sai số cho phép.
Thứ hai là nếu trong trường hợp x non-sparse tuy nhiên x lại sparse qua phép biến đổi tuyến tính T, thì cách xây dựng từ điển D( bao gồm các basis cho x) như thế nào ? (cái này chỉ là bài toán phụ không phải là bài toán chính (theo em hiểu) thì việc xây dựng từ điển sẽ cải thiện được \epsilon trong khi vẫn duy trì được performance của giải thuật)
Thứ ba là giải thuật khôi phục x' đó sẽ như thế nào để tối ưu performance e.g. tốc độ tính toán ?
Như vậy ba bài toán em phân loại này được xem là improtant to lĩnh vưc CS đúng không anh Bear ?
Như vậy là em sẽ quan tâm đến cả ba bài toán này cùng lúc anh nhỉ ? Nhưng mà theo cảm nhận của em thì cái này nó đòi trình toán cao quá, mà level em thì chắc hơn zero một epsilon à. Dậy bước tiếp theo là mình làm gì heng.
Quên mất, tình hình là em chưa có advisor, chưa có group để chơi cái này, liệu vấn đề nghiên cứu cái này có khả thi không anh ? Theo kinh nghiệm của mấy thằng bạn em thì nếu làm research thì nên dựa vào cái người khác đã làm rồi mình dựa vào đó để phát triển thêm, cho nên điều quan trọng là ý tưởng. Vì thế lại một câu hỏi lơ lửng trên đầu, ý tưởng từ đâu đây ?
He he, nhân tiện nhờ anh Bear làm advisor qua cái topic này ha !!!
P\S: Nếu thấy không cần thiết thì khỏi trả lời, em để lên đây để tracking theo ý anh.
Cái đoạn nhấn mạnh này của anh quan trọng à nha
Trích:
Mà thậm chí nhiều khi một bài toán ở một xó xỉnh nào đó không ai để ý, hoặc bài kiểu bổ củi khó không kém một bài toán thuộc dạng fundamental. Vấn đề là mình giành sức mình vào cái gì. Xác định đuợc cái gì là bài toán quan trọng, fundamental và có thể giải quyết đuợc, nhiều khi chiếm tới 60% công của bài báo.
Em đang gặp vấn đề nằm ở chỗ này !!!
thay đổi nội dung bởi: pandar bear, 11-06-2009 lúc 09:37 AM
Không biết ý anh Springer là gì ? Bài của bác Hưng viết quá đơn giản, có tính giới thiệu về eigenvalue và eigenvector. Cái em research có lẽ liên quan một chút đến PCA.
Thì tại tôi thấy ý tưởng chung khá giống với những kỹ thuật ấy. Cũng chuyển đổi ma trận, vector,... Phương pháp và mục đích có vẻ gần như thuật toán eigenfaces, dùng mấy phép biến đổi kiểu đó cho nhận dạng mặt.
__________________ Stay hungry, never foolish - Hãy cứ khát khao, nhưng chớ dại khờ
Giống mà không giống anh ơi, trước đây người ta nghiên cứu trên matrix A(m*n) là full rank m>=n. Bây giờ nó lại làm ngược lại m < n. Cho nên câu chuyện ở đây rất khác so với trước .
Nếu như ai học về xử lý tín hiệu thì cái này nó gọi là lấy mẫu dưới Nyquist. Tóm tắt một chút, theo Shanon thì tín hiệu muốn khôi phục lại được thì tần số lẫy mẫu phải ít nhất gấp đôi tần số cực đại của tín hiệu. Vấn đề là bây giờ người ta quan tâm tới việc lẫy mẫu dưới Nyquist, điều này có thể thực hiện được nếu tín hiệu là sparse hoặc compressible.
Theo thuần tuý toán học, bạn lấy 1 arbitrary orthogonal matrix size N, rồi lấy m hàng của matrix đó, sẽ là solution tối ưu cho matrix A. Bạn có thể dùng SVD để đưa về scalar rồi dùng KKT để chứng minh. Giả sử x là uncorrelated i.i.d. normal distribution nhé. Nếu kết hợp với các yếu tố khác của x, detection phụ thuộc vào knowledge của x, mà bạn ko cho biết gì cả.
Theo thuần tuý toán học, bạn lấy 1 arbitrary orthogonal matrix size N, rồi lấy m hàng của matrix đó, sẽ là solution tối ưu cho matrix A. Bạn có thể dùng SVD để đưa về scalar rồi dùng KKT để chứng minh.
KKT là cái này phải không anh ?
[Only registered and activated users can see links. ]
Trích:
Giả sử x là uncorrelated i.i.d. normal distribution nhé. Nếu kết hợp với các yếu tố khác của x, detection phụ thuộc vào knowledge của x, mà bạn ko cho biết gì cả.
Để đơn giản thì em chỉ bước đầu quan tâm đến x là K-sparse thôi. Các chỗ tô đậm anh có thể giải thích rõ hơn tại sao lại cần cái đó không ?
thay đổi nội dung bởi: pandar bear, 11-06-2009 lúc 10:37 PM
[Only registered and activated users can see links. ]
Để đơn giản thì em chỉ bước đầu quan tâm đến x là K-sparse thôi. Các chỗ tô đậm anh có thể giải thích rõ hơn tại sao lại cần cái đó không ?
KKT đúng là cái đó, vì x được giả sử như thế nên có covariance là identity nên solution là orthogonal. Còn nếu x có dạng khác, solution sẽ phụ thuộc vào thông tin của x mà chúng ta biết được chứ không đơn giản là 1 phần của orthogonal matrix. Em formulate cái problem đi, rồi tìm A để minimixe cái detection error. Tuỳ vào covariance hoặc độ summary của x sẽ có solution khác nhau.
Em không hiểu lắm, để em lấy một bài ví dụ mô phỏng của lão Emmanuel Candes ra đây rồi anh nói rõ hơn xem chứ em chả hình dung cách anh làm nó nằm chỗ nào.
Cụ thể cái code của nó đây:
% l1eq_example.m
%
% Test out l1eq code (l1 minimization with equality constraints).
%
% Written by: Justin Romberg, Caltech
% Email: [Only registered and activated users can see links. ]
% Created: October 2005
%
% put key subdirectories in path if not already there
path(path, './Optimization');
path(path, './Data');
% To reproduce the example in the documentation, uncomment the
% two lines below
load RandomStates
rand('state', rand_state);
randn('state', randn_state);
% signal length
N = 512;
% number of spikes in the signal
T = 20;
% number of observations to make
K = 120;
% random +/- 1 signal
x = zeros(N,1);
q = randperm(N);
x(q(1:T)) = sign(randn(T,1));
% measurement matrix
disp('Creating measurment matrix...');
A = randn(K,N);
A = orth(A')';
disp('Done.');
% observations
y = A*x;
% initial guess = min energy
x0 = A'*y;
% solve the LP
tic
xp = l1eq_pd(x0, A, [], y, 1e-3);
toc
% large scale
Afun = @(z) A*z;
Atfun = @(z) A'*z;
tic
xp = l1eq_pd(x0, Afun, Atfun, y, 1e-3, 30, 1e-8, 200);
toc
Em show kết quả hình ảnh đây cho anh xem
[Only registered and activated users can see links. ]
Từ trái qua phải,trên xuống a,b,c,d. Hình a là tín hiệu x có 20 entries +/-1 với độ dài là 512. Hình b là dùng minimization energy. Hình c là Histogram của Matrix đo A. Hình d là kết quả khôi phục dùng ell-1 linear programming.
disp('Creating measurment matrix...');
A = randn(K,N);
A = orth(A')';
===============================
Thì A chính là cái A anh nói đây, là K hàng của 1 cái orthogonal matrix size N. Có thể thay thế cái code này thành X=orth(randn(N));A=X(1:K,;
So sánh hình a và d thì thấy nó phục hồi tương đối tốt tín hiệu, vậy chú còn đòi gì nữa.
Cần nhờ góp ý về nghiên cứu của Panda 
!!!
