<p>There appear to be two user-introduced parameters $K,L$ in the algorithm you point to. Apart from that, the main task appears to be the computation of a pseudoinverse, and matrix multiplication. Without any further knowledge of the structure of the $n\times n$ matrix $A$, it would appear that the running time is $O(KL g(n))$, where $g(n)$ is your best estimate for computing the inverse and doing the multiplication. </p>

<p>Crudely, both of these can be bounded by $cn^3$, but there might be better answers based on your actual setting (if A is sparse, or if you use Strassen's matrix multiplication, and so on)</p>

CC BY-SA 2.5
2010-09-01T16:37:46.073Z
2010-09-01T16:37:46.073Z
Suresh Venkat
<p>I wanted to compute the complexity of a smoothed $\ell_0$ algorithm in BigO notation. The algorithm can be found <a href="http://ee.sharif.edu/~SLzero/SL0_ICASSP08.pdf" rel="nofollow">here</a>. Can anybody help me in this regard?</p>

CC BY-SA 2.5
2010-09-01T17:26:23.697Z
it would be helpful to expand the question so it's a little more self-contained. I.e try to specify the algorithm at a high level. Of course that in itself might have revealed the answer !
Suresh Venkat
<compressed-sensing>
Complexity of Smoothed $\ell_0$ algorithm
dazzlingtanish
# Complexity of Smoothed $\ell_0$ algorithm

(Asked by: username_0 on 2010-09-01)

I wanted to compute the complexity of a smoothed $\ell\_0$ algorithm in BigO notation. The algorithm can be found [here](http://ee.sharif.edu/~SLzero/SL0_ICASSP08.pdf). Can anybody help me in this regard?

**Tags:** compressed-sensing

> **Comments:**
> **username_1**: it would be helpful to expand the question so it's a little more self-contained. I.e try to specify the algorithm at a high level. Of course that in itself might have revealed the answer !  

---

## 1 answers

### Answer by username_1 on 2010-09-01. Score: 2

There appear to be two user-introduced parameters $K,L$ in the algorithm you point to. Apart from that, the main task appears to be the computation of a pseudoinverse, and matrix multiplication. Without any further knowledge of the structure of the $n\times n$ matrix $A$, it would appear that the running time is $O(KL g(n))$, where $g(n)$ is your best estimate for computing the inverse and doing the multiplication.

Crudely, both of these can be bounded by $cn^3$, but there might be better answers based on your actual setting (if A is sparse, or if you use Strassen's matrix multiplication, and so on)


---

