Fdtxjr

Is there anyway, I can have two passwords for my wi-fi

How to understand "he realized a split second too late was also a mistake"

Deciphering cause of death?

Overlapping circles covering polygon

How to test the sharpness of a knife?

What should be the ideal length of sentences in a blog post for ease of reading?

Does Doodling or Improvising on the Piano Have Any Benefits?

Anime with legendary swords made from talismans and a man who could change them with a shattered body

How can I, as DM, avoid the Conga Line of Death occurring when implementing some form of flanking rule?

Grepping string, but include all non-blank lines following each grep match

Why is the principal energy of an electron lower for excited electrons in a higher energy state?

What is the meaning of "You've never met a graph you didn't like?"

Should I assume I have passed probation?

Do I have to take mana from my deck or hand when tapping a dual land?

How to leave product feedback on macOS?

How do you justify more code being written by following clean code practices?

What's the name of the logical fallacy where a debater extends a statement far beyond the original statement to make it true?

Air travel with refrigerated insulin

Telemetry for feature health

Is there a RAID 0 Equivalent for RAM?

Given this phrasing in the lease, when should I pay my rent?

Would a primitive species be able to learn English from reading books alone?

Can I say "fingers" when referring to toes?

Isometric embedding of a genus g surface

Is there a fast way to compute the lowest eigenvalue of this symmetric PD matrix in this specific scenario?

Given an eigenvalue of a matrix, is the corresponding eigenvector unique?Does the lowest eigenvector have a nonvanishing component along a basis with the lowest diagonal value of a Hermitian matrix?Does the lowest diagonal element of a real symmetric matrix form an upper bound to the lowest eigenvalue?Is a symmetric positive definite matrix always diagonally dominant?The lower bound of the smallest eigenvalue of a symmetric positive definite matrixEigenvalue problem with symmetric matrix with diagonal diagonal blocksHow to compute the eigenvalues of a symmetric matrix?Multiplicity in the largest eigenvalue of a non-negative irreducible symmetric matrix (primitive and imprimitive matrix))Fast way of checking whether a matrix is positive definite without Cholesky decompositionHow to solve this linear matrix equation in fastest possible way, with lowest memory possible?

0

2

$begingroup$

Consider

$$C = A^H D A + M$$

where

• $A$ is a $m times m$ unitary matrix.




• $D$ is a $m times m$ diagonal matrix with entries either $0$ or $1$.
  The number of $1$'s is $n ll m$.




• $M$ is a $m times m$ diagonal matrix with all non-negative entries.

It is known that $C$ is a positive definite matrix. Is there a fast way to compute the lowest eigenvalue (need not compute the eigenvector) of $C$?

Especially given $n ll m$ and $m$ being very large I cannot afford to compute all $m$ eigenvalues. Also I would like to avoid storing a $m times m$ matrix in memory if possible.

linear-algebra eigenvalues-eigenvectors matrix-equations numerical-linear-algebra positive-definite

share|cite|improve this question

edited Mar 14 at 5:24

Rajesh Dachiraju

asked Mar 12 at 21:55

Rajesh DachirajuRajesh Dachiraju

1,06942768

$endgroup$

This question has an open bounty worth +100
reputation from Rajesh Dachiraju ending ending at 2019-03-27 01:01:36Z">in 6 days.

This question has not received enough attention.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @RodrigodeAzevedo : C is PD. (otherwise PSD means smallest eigen value is zero no?)
  $endgroup$
  – Rajesh Dachiraju
  Mar 14 at 4:50
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @RodrigodeAzevedo : if you are asking $C$ is symmetric, then yes. $C$ is symmetric positive definitive. (SPD)
  $endgroup$
  – Rajesh Dachiraju
  Mar 14 at 4:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How are you storing $A$ if you cannot store $mtimes m$ matrices? Are you operating $Au$ implicitly?
  $endgroup$
  – Y. S.
  23 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Y.S. : I have a closed form expression/formula to generate entries of A. Look at D. I dont need to store entire A due to D. matrices A and M are fixed constants, D is the input to the algorithm. D is the one that varies.
  $endgroup$
  – Rajesh Dachiraju
  23 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Y.S. : some approach : $B=A^HDA$ is a $mtimes m$ symmetric PSD with top $n$ eigen values equal to $1$ and the remaining $(m−n)$ being zero. $n<<m$
  $endgroup$
  – Rajesh Dachiraju
  23 hours ago
  

  
  
  
  

 | 
show 12 more comments

0

2

$begingroup$

Consider

$$C = A^H D A + M$$

where

• $A$ is a $m times m$ unitary matrix.




• $D$ is a $m times m$ diagonal matrix with entries either $0$ or $1$.
  The number of $1$'s is $n ll m$.




• $M$ is a $m times m$ diagonal matrix with all non-negative entries.

It is known that $C$ is a positive definite matrix. Is there a fast way to compute the lowest eigenvalue (need not compute the eigenvector) of $C$?

Especially given $n ll m$ and $m$ being very large I cannot afford to compute all $m$ eigenvalues. Also I would like to avoid storing a $m times m$ matrix in memory if possible.

linear-algebra eigenvalues-eigenvectors matrix-equations numerical-linear-algebra positive-definite

share|cite|improve this question

edited Mar 14 at 5:24

Rajesh Dachiraju

asked Mar 12 at 21:55

Rajesh DachirajuRajesh Dachiraju

1,06942768

$endgroup$

This question has an open bounty worth +100
reputation from Rajesh Dachiraju ending ending at 2019-03-27 01:01:36Z">in 6 days.

This question has not received enough attention.

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @RodrigodeAzevedo : C is PD. (otherwise PSD means smallest eigen value is zero no?)
  $endgroup$
  – Rajesh Dachiraju
  Mar 14 at 4:50
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @RodrigodeAzevedo : if you are asking $C$ is symmetric, then yes. $C$ is symmetric positive definitive. (SPD)
  $endgroup$
  – Rajesh Dachiraju
  Mar 14 at 4:58
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How are you storing $A$ if you cannot store $mtimes m$ matrices? Are you operating $Au$ implicitly?
  $endgroup$
  – Y. S.
  23 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Y.S. : I have a closed form expression/formula to generate entries of A. Look at D. I dont need to store entire A due to D. matrices A and M are fixed constants, D is the input to the algorithm. D is the one that varies.
  $endgroup$
  – Rajesh Dachiraju
  23 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @Y.S. : some approach : $B=A^HDA$ is a $mtimes m$ symmetric PSD with top $n$ eigen values equal to $1$ and the remaining $(m−n)$ being zero. $n<<m$
  $endgroup$
  – Rajesh Dachiraju
  23 hours ago
  

  
  
  
  

 | 
show 12 more comments

$begingroup$

Consider

$$C = A^H D A + M$$

where

• $A$ is a $m times m$ unitary matrix.




• $D$ is a $m times m$ diagonal matrix with entries either $0$ or $1$.
  The number of $1$'s is $n ll m$.




• $M$ is a $m times m$ diagonal matrix with all non-negative entries.

It is known that $C$ is a positive definite matrix. Is there a fast way to compute the lowest eigenvalue (need not compute the eigenvector) of $C$?

Especially given $n ll m$ and $m$ being very large I cannot afford to compute all $m$ eigenvalues. Also I would like to avoid storing a $m times m$ matrix in memory if possible.

linear-algebra eigenvalues-eigenvectors matrix-equations numerical-linear-algebra positive-definite

share|cite|improve this question

edited Mar 14 at 5:24

Rajesh Dachiraju

asked Mar 12 at 21:55

Rajesh DachirajuRajesh Dachiraju

1,06942768

$endgroup$

share|cite|improve this question

edited Mar 14 at 5:24

Rajesh Dachiraju

asked Mar 12 at 21:55

Rajesh DachirajuRajesh Dachiraju

1,06942768

share|cite|improve this question

edited Mar 14 at 5:24

Rajesh Dachiraju

asked Mar 12 at 21:55

Rajesh DachirajuRajesh Dachiraju

1,06942768

asked Mar 12 at 21:55

Rajesh DachirajuRajesh Dachiraju

1,06942768

asked Mar 12 at 21:55

Rajesh DachirajuRajesh Dachiraju

1,06942768

1 Answer
1

active

oldest

votes

2

$begingroup$

There are many ways to do this. One way would be inverse iteration, which is essentially power iteration with $C^-1$. However, this requires a solve at each step.

Another possibility is to observe that the matrix $alpha I - C$ will has eigenvalues $alpha - lambda_i$ where $lambda_i$ is an eigenvalue of $C$. Therefore, if we pick $alpha$ so that $|alpha-lambda_min| > |alpha - lambda_i|$ for all $lambda_i$ except $lambda_min$ the top eigenvalue of $alpha I - C$ will correspond to the bottom eigenvalue of $C$. We can then compute the top eigenvalue of $I - alpha C$ which will give us the smallest eigenvalue of $C$.

A simple way to ensure this is to pick $alpha > lambda_max$. If you want, you could compute the top eigenvalue of $C$ and use this. Otherwise you could use the fact that, $lambda_max(C) leq lambda_max(A^HDA) + lambda_max(M) leq 1 + lambda_max(M)$

share|cite|improve this answer

edited 9 hours ago

answered Mar 13 at 20:55

tchtch

823310

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3145752%2fis-there-a-fast-way-to-compute-the-lowest-eigenvalue-of-this-symmetric-pd-matrix%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

There are many ways to do this. One way would be inverse iteration, which is essentially power iteration with $C^-1$. However, this requires a solve at each step.

Another possibility is to observe that the matrix $alpha I - C$ will has eigenvalues $alpha - lambda_i$ where $lambda_i$ is an eigenvalue of $C$. Therefore, if we pick $alpha$ so that $|alpha-lambda_min| > |alpha - lambda_i|$ for all $lambda_i$ except $lambda_min$ the top eigenvalue of $alpha I - C$ will correspond to the bottom eigenvalue of $C$. We can then compute the top eigenvalue of $I - alpha C$ which will give us the smallest eigenvalue of $C$.

A simple way to ensure this is to pick $alpha > lambda_max$. If you want, you could compute the top eigenvalue of $C$ and use this. Otherwise you could use the fact that, $lambda_max(C) leq lambda_max(A^HDA) + lambda_max(M) leq 1 + lambda_max(M)$

share|cite|improve this answer

edited 9 hours ago

answered Mar 13 at 20:55

tchtch

823310

$endgroup$

add a comment | 

2

$begingroup$

There are many ways to do this. One way would be inverse iteration, which is essentially power iteration with $C^-1$. However, this requires a solve at each step.

Another possibility is to observe that the matrix $alpha I - C$ will has eigenvalues $alpha - lambda_i$ where $lambda_i$ is an eigenvalue of $C$. Therefore, if we pick $alpha$ so that $|alpha-lambda_min| > |alpha - lambda_i|$ for all $lambda_i$ except $lambda_min$ the top eigenvalue of $alpha I - C$ will correspond to the bottom eigenvalue of $C$. We can then compute the top eigenvalue of $I - alpha C$ which will give us the smallest eigenvalue of $C$.

A simple way to ensure this is to pick $alpha > lambda_max$. If you want, you could compute the top eigenvalue of $C$ and use this. Otherwise you could use the fact that, $lambda_max(C) leq lambda_max(A^HDA) + lambda_max(M) leq 1 + lambda_max(M)$

share|cite|improve this answer

edited 9 hours ago

answered Mar 13 at 20:55

tchtch

823310

$endgroup$

add a comment | 

$begingroup$

There are many ways to do this. One way would be inverse iteration, which is essentially power iteration with $C^-1$. However, this requires a solve at each step.

Another possibility is to observe that the matrix $alpha I - C$ will has eigenvalues $alpha - lambda_i$ where $lambda_i$ is an eigenvalue of $C$. Therefore, if we pick $alpha$ so that $|alpha-lambda_min| > |alpha - lambda_i|$ for all $lambda_i$ except $lambda_min$ the top eigenvalue of $alpha I - C$ will correspond to the bottom eigenvalue of $C$. We can then compute the top eigenvalue of $I - alpha C$ which will give us the smallest eigenvalue of $C$.

A simple way to ensure this is to pick $alpha > lambda_max$. If you want, you could compute the top eigenvalue of $C$ and use this. Otherwise you could use the fact that, $lambda_max(C) leq lambda_max(A^HDA) + lambda_max(M) leq 1 + lambda_max(M)$

share|cite|improve this answer

edited 9 hours ago

answered Mar 13 at 20:55

tchtch

823310

$endgroup$

share|cite|improve this answer

edited 9 hours ago

answered Mar 13 at 20:55

tchtch

823310

answered Mar 13 at 20:55

tchtch

823310

answered Mar 13 at 20:55

tchtch

823310