phương pháp nhanh cho xấp xỉ 3 giá trị riêng và vector riêng cao nhất của một ma trận đối xứng lớn

Question

Tôi viết code để tính toán Classical Multidimensional Scaling (viết tắt là MDS) của một rất lớn n bởi n ma trận, n = 500,000 trong ví dụ của tôi.

Trong một bước của MDS, tôi cần tính ba số cao nhất là eigenvalues and their corresponding eigenvectors của n bởi n ma trận. Ma trận này được gọi là ma trận B. Tôi chỉ cần ba đặc tính riêng này và các giá trị riêng. Các phương pháp phổ biến để tính toán các giá trị riêng và các giá trị riêng của một ma trận lớn mất một thời gian dài, và tôi không đòi hỏi một câu trả lời rất chính xác, vì vậy tôi đang tìm kiếm ước tính về các giá trị riêng và giá trị riêng.

Một số thông số:

1. Ma trận B là symmetric, real, và khá dense
2. Sự phân hủy eigenvalue của B về mặt lý thuyết phải luôn luôn tạo ra các số thực.
3. Tôi không yêu cầu ước tính chính xác hoàn toàn, chỉ là ước tính nhanh. Tôi cần nó để hoàn thành sau vài giờ nữa.
4. tôi viết trong python và C++

Câu hỏi của tôi: Có phương pháp nhanh chóng của ước lượng ba vector riêng cao nhất và giá trị riêng của một B ma trận lớn như vậy?

Tiến độ của tôi: Tôi đã tìm thấy một số method of approximating the highest eigenvalue of a matrix, nhưng tôi không biết liệu tôi có thể khái quát hóa nó thành ba số cao nhất hay không. Tôi cũng đã tìm thấy this paper written in 1996, nhưng nó là cực kỳ kỹ thuật và khó khăn cho tôi để đọc.

Answer 1

G. Golub và CF Vân Loan Matrix 2 trong chương 9 trạng thái đó thuật toán Lanczos là một trong những lựa chọn này tính toán (trừ rằng ma trận lý tưởng nên thưa thớt - nó hoạt động rõ ràng cho những người không thưa thớt cũng)

https://en.wikipedia.org/wiki/Lanczos_algorithm

Answer 2

Bạn có thể nhận được eigenvector cao nhất của B và sau đó, chuyển đổi dữ liệu thành B' bằng cách sử dụng eigenvector đó. Sau đó, bật cột đầu tiên của B' và nhận được B'' để bạn có thể nhận được eigenvector cao nhất của B'': đó là đủ thông tin để soạn một bản địa chính xác cao thứ hai cho B. Và sau đó cho thứ ba.

Giới thiệu về tốc độ: bạn có thể lấy mẫu ngẫu nhiên tập dữ liệu khổng lồ đó để chỉ là tập dữ liệu của N mục. Nếu bạn chỉ nhận được ba chiều, tôi hy vọng bạn cũng có thể loại bỏ hầu hết dữ liệu để có cái nhìn tổng quan về các đặc tính riêng. Bạn có thể gọi nó: 'cuộc thăm dò bầu cử'. Tôi không thể giúp bạn trong việc đo lường tỷ lệ lỗi, nhưng tôi sẽ cố gắng lấy mẫu 1k mục, nhiều lần, và nhìn thấy nếu kết quả là nhiều hơn hoặc ít hơn như nhau.

Bây giờ bạn có thể nhận được ý nghĩa của một số 'cuộc thăm dò ý kiến' để xây dựng một 'dự đoán'.

Answer 3

Có xem xét lời đề nghị trong chủ đề này

Largest eigenvalues (and corresponding eigenvectors) in C++

Như đã đề cập ở đó bạn có thể sử dụng ARPACK gói trong đó có một giao diện ++ C.