If you specify a linear function $f$, it won't really change the problem significantly.

@nathan.j.mcdougall, yes the issue is my function is non-linear. I added a new sentence, thanks for pointing out.

You use $f$ on both matrices and vectors. How should that extension be interpreted? Or is $f$ an element-wise function?

@nathan.j.mcdougall element wise.

If there is any solution to the original problem, the solution to the transformed problem will be identical, except it would have $f(A)$ instead of $A$, and $f(b)$ instead of $b$. The only way using $f$ would be useful, then, would be if there is a value of $A^*$ and $b^*$ which makes the problem significantly easier, which we can "force" $f$ to map to. The obvious example is $f=0$, but that's linear. I'm very skeptical that there's anything else.

I believe that, if $A$ is full-rank, then $x=(A^T A)^{-1}(A^T b+\lambda)$ is a global minimum for every $\lambda\in [-\frac{1}{2},\frac{1}{2}]^{n}$, where $n$ is the number of elements in $x$. That is from taking subgradients. So I think if you can focus on choosing $f$ to make $A$ as likely as possible to be full rank, perhaps just by making $f$ a 'scramble' function, then you can get that closed form solution.

@nathan.j.mcdougall, very interesting comments, thank you. In a different note, if the function is not element-wise but based on average of say n samples; any insights for such case?

I do not really understand what you mean by "based on average of n samples", sorry.

I am creating a matrix A from one vector such that it is shifted in each column. This vector is present somewhere in the long vector b. And I want to find in which column of A the vector b is. Am I making sense so far.

If so, why wouldn't you just check each column individually?

Yes, I can do that but I expect the convex optimization tool does the same thing is not it?

The original 'b' is highly noisy, I also know the signal what I am looking for. After average the noise is reduced considerably. Hence the effort is to see if one can extract signal from the noise floor.

Ah, so b isn't contained exactly in A

There is noise

I see

yes.

So would I then be correct to interpret "based on an average of n samples" as more or less "as a function of the rows"?

Not exactly.

Hmm, so I still don't really follow I'm afraid.

I take moving average of say n samples of b and pass it through a nonlinear function and gets the desired b.

Next, I do the same operation of the known signal that I am looking for make A shifting in each column

Next, I do the same operation of the known signal that I am looking for and create thee matrix A by shifting the vector in each column. The matrix A is very sparse

Okay. I don't really see how that affects the problem

in the sense that the average of b just "looks like" b to the function f

Yes, it may not.

It might make your solution more accurate

but I don't think it will change your strategy for choosing f

If I do only average and do the same thing my solution looks normal.

There is no problem.

Maybe this is naive, but have you tried correlation-based methods?

But if I pass the average value though a non-linear function and do the same, I get very odd result.

Or if they are periodic signals, fourier-based ones?

And I am trying to understand why. I was expecting to get similar sparse results as I got only for average alone.

Well, the non-linear function will not necessarily preserve the structure of the original problem

if for example you choose f=0

you loose all the structure

and the solution x=0

is basically meaningless

so non-linear functions in general will not always give you not-odd results.

Yes, it is not so naive non-linear function.

As you can see generally Matched filter is used for such detection problem

Yes, non-linear function will not preserve the original structure. I was looking for non-linear function which may transform my problem to a better structure.

But getting very non-spare solution makes me wonder why?

I have considered a constant signal now.

Yes. I think if you explore functions of each signal individually (functions of columns of A), rather than each element individually (functions of elements of A) you will have more success. For example, a DFT would give you useful information in the frequency domain, if this is a time-based problem. You can't do anything like that by restricting yourself to element-wise functions.

But I agree that it's a bit strange that you are getting odd results by considering simple cases.

So the question does the constant signal preserve the structure in some domain.

Yes, DFT operation would give me frequencies but I am purely on time domain now.