2 '유사한'행렬을 취하고 하나를 '정렬'하는 알고리즘

우선, 간결한 어휘가 부족하기 때문에 제목이 매우 나쁩니다. 내가하는 일을 설명하고 다시 질문을 해보겠습니다.2 '유사한'행렬을 취하고 하나를 '정렬'하는 알고리즘

배경

정보의 내가 n 실험 관찰 벡터의 수입니다 크기 n X m, 2 행렬 있다고 가정 해 봅시다, 길이 m (관찰이 수집하는 동안 시간 시리즈)의 각. 이 행렬 중 하나는 S이라는 원래 행렬이고 다른 하나는 S의 재구성 된 버전 인 Y입니다.

는의가 Y 제대로 S를 재구성한다고 가정하자. 그러나 재구성 알고리즘의 한계로 인해 Y은 S에있는 벡터의 진폭을 확인할 수 없으며 해당 벡터에 적절한 부호를 제공 할 수도 없습니다 (벡터가 뒤집힐 수도 있음). 또한 관찰 벡터의 순서가 Y 인 경우 해당 벡터의 원래 순서가 S과 일치하지 않을 수 있습니다.

질문

알고리즘 또는 S-Y의 "재정렬"인 새로운 행렬을 생성하는 기술이 존재하도록 Y 및 S 정규화되는 경우, 알고리즘 (1) S에있는 벡터와 일치하는 Y의 벡터를 찾고 벡터의 원래 순서를 복원하고 (2) 마찬가지로 벡터의 부호와 일치합니까?

언제나처럼, 나는 정말로 모든 도움을 주셔서 감사합니다. 감사!

출처

2009-08-20 oort

이게 숙제입니까? 사촌 나는 누군가가 실생활에서 이것을 필요로 할 것이라고 상상할 수 없다. 이미 그것을 해결하는 방법을 모른다. – zvolkov

zvolkov : 아니 숙제가 아니다 ...그리고 저는 Yuval A가 제공 한 방법을 이미 생각했습니다. 그러나 매우 큰 데이터 세트를 가지고있을 가능성이 있습니다. 가능한 경우 이차 시간 메서드를 피하려고합니다. 더 빠른 것이 있는지 궁금해하고있었습니다. 이 일을하는 법을 알지 못하는 것에 관해서는 ... 글쎄, 그래서 내가 묻는거야. – oort

벡터가 어떻게 엉망이 될지에 대한 정보 나 제한 사항이 없으므로 Yuval의 프로세스에 집착하고 있다고 생각됩니다. 재구성 알고리즘을 제공 한 경우 속도를 높이기 위해 악용 될 수있는 속성이있을 수 있습니다. –

두 행렬의 각 벡터에 대한 정규화 된 형식을 간단히 계산하고 비교하는 방법은 어떻습니까? 그러면 각 행렬의 각 벡터에 대해 일대일로 정확하게 일치해야합니다.

벡터의 일반적인 형태를 준수 하나이다 : ||v||는 벡터 유클리드 규범

v_norm = v/||v||

. v=(v1, v2, ..., vn)의 경우 ||v|| = sqrt(v1^2 + ... + vn^2)입니다.

거기에서 순서를 재구성하고 각 벡터의 원래 길이와 방향 (벡터 또는 그 반대)을 반환 할 수 있습니다.

알고리즘은 여기부터 상당히 간단해야하며 구현을 결정해야합니다. ~~이 메서드는 2 차 복잡성~~ 이어야합니다. 의견에 따르면이 알고리즘에서는 실제로 O(nlogn)의 복잡성을 달성 할 수 있습니다. 그보다 나은 것을 필요로한다면, 선형 복잡성 - 구체적으로, 지금 당장 생각할 수없는 훨씬 복잡한 알고리즘이 필요합니다.

출처

2009-08-20 16:26:58

왜 이차원입니까? Y와 S의 각 벡터를 미리 정렬 된 행 번호와 함께 정렬하면 행마다 쉽게 일치시킬 수 있습니다. 또한 각 벡터의 첫 번째 0이 아닌 요소가 양수가되도록 기호를 정규화해야합니다. 그런 다음 모두 n log n입니다. – xan

2 '유사한'행렬을 취하고 하나를 '정렬'하는 알고리즘

답변

관련 문제