All Questions
Tagged with recursive-algorithms matrices
26
questions
0
votes
1
answer
28
views
Fast algorithms for computing $AGA^T$ with $G$ PSD symmetric.
Problem:
In the context of decision making in some optimization problems, I found that it is meaningful to compute $AGA^T$ with $A\in\mathbb R^{m\times n}$ and $G\in\mathbb R^{n\times n}$ a PSD ...
- 6,076
0
votes
0
answers
1k
views
Multiplying two matrices using a recursive algorithm
I'd like to step thru the algorithm below to see if I understand how it works.
...
- 123
1
vote
1
answer
85
views
Converting recursive equation into matrices
Here is example of converting fibonacci function into matrices.
Fibonacci sequence defines
$$
f(1)=1
$$
$$
f(2)=1
$$
$$
f(x) = f(x-1) + f(x-2)
$$
It can be converted into matrix
$$
\begin{bmatrix}
1 &...
0
votes
0
answers
42
views
Proving constant-time algorithm to find $A_n \mod 50$ as a linear combination of the $k$ previous $A$ terms [duplicate]
I've got the below scenario, based on a practice problem:
Suppose a sequence of integers $A_n$, and $A_0,\ldots,A_{k-1}< 50$ are all given, and each $A_i$ is a linear combination of the previous $k$...
- 75
1
vote
0
answers
42
views
Applications of Products of Random Matrices
I'm studying the paper "Matrix concentration for products" and I'm trying to find simple applications of the inequalities for the expected value of the spectral norm of products of random ...
- 281
2
votes
1
answer
42
views
Matrix method to solve linear recceurences with slight variations
How can we construct a matrix to define linear reccurence relations such as
$F_{\mathrm{i}} =2F_{\mathrm{i-1}} + 3F_{\mathrm{i-2}} + 5$ and
$F_{\mathrm{i}} =F_{\mathrm{i-1}} +2\mathrm{i^2} + 3\mathrm{...
1
vote
0
answers
26
views
How many calls of the form $\det(B)$ does the algorithm create?
Let's say $A\in \mathbb{R}^{n\times n}$ and the $n^2$ components of $A$ are pairwise different. In order to calculate $\det(A)$ we can use the recursive algorithm that computes $\det(A) = \sum\limits_{...
- 2,649
0
votes
0
answers
68
views
Closed form of recursive sequences
Suppose that I have sequences $\{\alpha_n,\beta_n:n\in\mathbb{N}\}$ and consider the sequence
$(x_n)$ defined recursively by:
$$\begin{cases}x_0=a\\ x_1=b\\ x_{n+1}=\alpha_n \cdot x_n + \beta_n\cdot ...
- 4,880
1
vote
2
answers
3k
views
derivation of fibonacci log(n) time sequence
I was trying to derive following equation to compute the nth fibonacci number in O(log(n)) time.
F(2n) = (2*F(n-1) + F(n)) * F(n)
which i found on wiki form the ...
- 121
1
vote
0
answers
403
views
Coppersmith-Winograd algorithm
I'm interested in algorithms to compute matrix multiplications. Is the Coppersmith-Winograd algorithm similar to the Strassen algorithm ?
I have two other questions:
1) Are the multiplications done ...
- 435
2
votes
0
answers
675
views
Trace and transpose of a Matrix
I have a recurrence relation as follows
$ \left\{
\begin{array}{ll}
R_0=H & \mbox{if } n = 0 \\
R_1 =sR_0 \hspace{.1cm} A & \mbox{if }n=1\\
R_{n+2} =\frac{s}{n+2}\{ R_{n+1} \...
- 1,717
1
vote
0
answers
65
views
Recurrence Derivative
I have a recurrence relation as follows
$ \left\{
\begin{array}{ll}
R_0=H & \mbox{if } n = 0 \\
R_1(s)=sR_0 \hspace{.1cm} A & \mbox{if }n=1\\
R_{n+2}(s)=\frac{s}{n+2}\{ R_{n+...
- 1,717
2
votes
1
answer
160
views
Recurrence - using power series
Could you help me in solving this recursion( a closed form ) using power series
$\mu(n)=\mu(n−1)k_0+(n−1)\mu(n−2) k_1 \tag 1$,
where $k_0,k_1$ are constants $\mu(0)=3,\mu(1)=5$
HINT: We can think ...
- 1,717
3
votes
1
answer
3k
views
The Matrix Inversion Lemma: the General Case
I find it is hard to understand the application senario of the Matrix Inversion Lemma in non-special cases. Suppose I already computed $A^{-1}$ and want to find $\left(A+UCV \right)^{-1}$. The Matrix ...
- 41
0
votes
0
answers
305
views
Why can I not generalize O(n^log5) for squaring matrice of size n
I have a question that is bugging me for around a 3 days, I first asked this question in stackoverflow but no one could answer it reasonably though they tried to help, so finally I found here as a ...
- 123